Submission #73495174

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
typedef long long ll;
typedef pair<ll,ll> PII;
typedef array<ll,2> a2;
typedef array<ll,3> a3;
int n,m,k;
int a[N];

vector<int> e[N],e2[N];
ll sum[N];
ll mn[N];
bool tf[N];
int cnt[N];
set<int> se;
void 打卡啦摩托(){
    cin>>n>>m;
    vector<a2> vec;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        if(x==y) continue;
        if(x<y)
        vec.push_back({x,y});
        // if(x>y) swap(x,y);
        e[x].push_back(y);
        e2[y].push_back(x);
    }
    for(int i=1;i<=n;i++) sort(e[i].begin(),e[i].end());
    for(int i=1;i<=n;i++){
        sort(e2[i].begin(),e2[i].end());
        if(e2[i].size()){
            int t=e2[i][0];
            // cout<<t<<" "<<i<<endl;
            if(t<i){
                sum[t]++;
                sum[i]--;
            }
        }
    }
    for(int i=1;i<=n;i++) sum[i]+=sum[i-1];
    priority_queue<a2,vector<a2>,greater<a2>> q;
    memset(mn,0x3f,sizeof mn);
    mn[1]=0;
    q.push({0,1});
    while(q.size()){
        auto tp=q.top();
        q.pop();
    
        int id=tp[1];
        if(tf[id]) continue;
        tf[id]=1;
        int nw=max(mn[id],1ll*id);
        for(auto j:e[id]){
            if(mn[j]>nw){
                mn[j]=nw;
                q.push({mn[j],j});
            }
        }
    }    
    ll mx=0;
    for(int i=1;i<=n;i++){
        mx=max(mx,mn[i]);
        if(i<mx) cout<<-1<<"\n";
        else cout<<sum[i]<<"\n";
    }

}


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _=1;
    // cin>>_;
    while(_--){
        打卡啦摩托();
    }
}

Submission Info

Judge Result