Submission #1108786

---

Source Code Expand

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

#define fin "\n"

#define FOR(i,bg,ed) for(int i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
template <typename T>
inline void chmin(T &l,T r){l=min(l,r);}
template <typename T>
inline void chmax(T &l,T r){l=max(l,r);}

typedef tuple<LL,int,int> T;
typedef pair<int,int> P;

#define fi first
#define se second
int N,Q;
map<int,int> rg;
priority_queue<T,vector<T>,greater<T>> que;
T abc[212345];
int used[212345];
bool in_range(LL a){
    auto nxt=rg.lower_bound(a);
    return (nxt!=rg.end()&&nxt->se<=a);
}
int  add_range(LL a){
    if(in_range(a))return 0;
    auto nxt=rg.lower_bound(a);
    if(nxt!=rg.end()&&nxt->se==a+1){
        //a-1] a [a+1
        if(rg.count(a-1)==1){
            int bg=rg[a-1];
            int ed=nxt->first;
            rg.erase(a-1);
            rg[ed]=bg;
        }
        //null a [a+1
        else{
            int bg=a;
            int ed=nxt->fi;
            rg[ed]=bg;
        }
    }
    else{
        //a-1] a null
        if(rg.count(a-1)==1){
            int bg=rg[a-1];
            int ed=a;
            rg.erase(a-1);
            rg[ed]=bg;
        }
        //null a null
        else{
            int bg=a;
            int ed=a;
            rg[ed]=bg;
        } 
    }
    return 1;
}
LL get_nxt(int &a,int &b){
    LL prev_a=a;
    LL prev_b=b;
    LL na=rg.lower_bound(a)->fi+1;
    LL nb=rg.lower_bound(b)->fi+1;
    LL cost;
    if(na-a>=nb-b){
        na=a+(nb-b-1);
        cost=na-a+nb-b;
        b=na%N;
        a=nb%N;
    }
    else{
        nb=b+(na-a);
        cost=na-a+nb-b;
        b=nb%N;
        a=na%N;
    }
    return cost;
}

int main(){
    scanf("%d %d",&N,&Q);
    vector<vector<int>> g(N);
    int rest=N;
    LL res=0;
    REP(i,Q){
        int a,b;LL c;
        scanf("%d %d %lld",&b,&a,&c);
        if(a==b)b=(b+1)%N,c++;
        abc[i]=T(c,a,b);
        g[a].push_back(i);
        g[b].push_back(i);
    }
    REP(i,Q)used[i]=0;
    //init
    {
        int id=0;
        REP(i,Q)
            if(abc[i]<abc[id])
                id=i;
        int a,b;LL c;
        tie(c,a,b)=abc[id];
        rest-=add_range(a);add_range(a+N);
        rest-=add_range(b);add_range(b+N);
        res+=c;
        
        while(g[a].size()){
            if(!used[g[a].back()]){
                que.push(abc[g[a].back()]);
            }
            used[g[a].back()]=1;
            g[a].pop_back();
        }
        while(g[b].size()){
            if(!used[g[b].back()]){
                que.push(abc[g[b].back()]);
            }
            used[g[b].back()]=1;
            g[b].pop_back();
        }
    }
    while(rest){
        auto top=que.top();que.pop();
        int a,b;LL c;

        tie(c,a,b)=top;
        //cout<<a<<" "<<b<<" "<<c<<endl;
        if(!in_range(a)){
            // cout<<a<<" "<<b<<" "<<c<<endl;
            res+=c;
            rest-=add_range(a);add_range(a+N);
            while(g[a].size()){
                if(!used[g[a].back()]){
                    que.push(abc[g[a].back()]);
                }
                used[g[a].back()]=1;
                g[a].pop_back();
            }
        }
        else if(!in_range(b)){
            //cout<<a<<" "<<b<<" "<<c<<endl;
            res+=c;
            rest-=add_range(b);add_range(b+N);
            while(g[b].size()){
                if(!used[g[b].back()]){
                    que.push(abc[g[b].back()]);
                }
                used[g[b].back()]=1;
                g[b].pop_back();
            }

        }
        c+=get_nxt(a,b);
        que.push(T(c,a,b));
    }

    
    
    cout<<res<<endl;

    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:87:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&N,&Q);
                         ^
./Main.cpp:93:37: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %lld",&b,&a,&c);
                                     ^

Judge Result