Submission #76688160

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#include "atcoder/all"
using namespace atcoder;
#define rep(i, n) for (int i = 0; i < (n); ++i)
//using mint=modint998244353;
void solve(){
    int n,m;
    cin>>n>>m;
    vector<pair<int,int>>a(m);
    rep(i,m)cin>>a[i].first>>a[i].second;
    sort(a.begin(),a.end());
    vector<int>ans(n,1);
    set<int>s,u;
    int t=0,ma=-1;
    rep(i,n){
        if(t<m){
            while(i==a[t].first-1){
            if(ma<i){
                s=u;
                for(int j=i;j<a[t].second;j++){
                    ans[j]=j-i+1;
                    s.insert(j-i+1);
                }
            }
            else{
                if(a[t].second>ma){
                    int co=1;
                    for(int j=ma+1;j<a[t].second;j++){
                        while(s.count(co))co++;
                        ans[j]=co;
                        s.insert(co);
                    }
                }
            }
            if(a[t].second>ma)ma=a[t].second-1;
            t++;
            if(t==m)break;
        }
    }
    s.erase(ans[i]);
    }
    rep(i,n)cout<<ans[i]<<' ';
    cout<<endl;
}
int main(){
    ios::sync_with_stdio(false);
	cin.tie(nullptr);
    int t=1;
    cin>>t;
    while(t--)solve();
}

Submission Info

Judge Result