Submission #738209

#	Time	Username	Problem	Language	Result	Execution time	Memory
738209		mosiashvililuka	RMQ (NOI17_rmq)	C++14	100 / 100	175 ms	8624 KiB

rmq

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,tes,t,L[100009],R[100009],ans[100009],seg[400009],SEG[400009],seg2[400009],l,r,z,zz,za;
pair <pair <int, int>, int> p[100009];
vector <pair <int, int> > v[100009];
void NO(){
    for(i=1; i<=a; i++){
        cout<<"-1 ";
    }
    exit(0);
}
void pushdown(int q, int w, int rr){
    if(q!=w){
        seg2[rr*2]+=seg2[rr];
        seg2[rr*2+1]+=seg2[rr];
    }
    seg[rr]+=seg2[rr];
    seg2[rr]=0;
}
void upd(int q, int w, int rr){
    pushdown(q,w,rr);
    if(q>r||w<l) return;
    if(q>=l&&w<=r){
        seg2[rr]+=z;
        pushdown(q,w,rr);
        return;
    }
    upd(q,(q+w)/2,rr*2);
    upd((q+w)/2+1,w,rr*2+1);
    if(seg[rr*2]<=seg[rr*2+1]){
        seg[rr]=seg[rr*2];
        SEG[rr]=SEG[rr*2];
    }else{
        seg[rr]=seg[rr*2+1];
        SEG[rr]=SEG[rr*2+1];
    }
}
void read(int q, int w, int rr){
    pushdown(q,w,rr);
    if(q>r||w<l) return;
    if(q>=l&&w<=r){
        if(z>seg[rr]){
            z=seg[rr];zz=SEG[rr];
        }
        return;
    }
    read(q,(q+w)/2,rr*2);
    read((q+w)/2+1,w,rr*2+1);
}
int main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>a>>tes;
    for(t=1; t<=tes; t++){
        cin>>p[t].first.first>>p[t].first.second>>p[t].second;
        p[t].first.first++;p[t].first.second++;
    }
    za=1;
    while(za<a) za*=2;
    for(i=1; i<=a; i++){
        seg[za+i-1]=0;SEG[za+i-1]=i;seg2[za+i-1]=0;
    }
    for(i=za-1; i>=1; i--){
        seg[i]=seg[i*2];
        SEG[i]=SEG[i*2];
    }
    for(i=0; i<a; i++){
        L[i]=1;R[i]=a;
    }
    for(t=1; t<=tes; t++){
        c=p[t].first.first;d=p[t].first.second;e=p[t].second;
        L[e]=max(L[e],c);
        R[e]=min(R[e],d);
        v[e].push_back({c,d});
        l=c;r=d;z=1;
        upd(1,za,1);
    }
    for(i=0; i<a; i++){
        if(L[i]>R[i]){
            NO();
        }
    }
    for(i=0; i<a; i++){
        for(vector <pair <int, int> >::iterator it=v[i].begin(); it!=v[i].end(); it++){
            l=(*it).first;r=(*it).second;z=-1;
            upd(1,za,1);
        }
        c=L[i];d=R[i];
        l=c;r=d;z=tes+4;zz=0;
        read(1,za,1);
        //cout<<i<<": "<<l<<" "<<r<<"    "<<z<<" "<<zz<<"\n";
        if(z==0){
            ans[zz]=i;
            l=zz;r=zz;z=tes+4;
            upd(1,za,1);
        }else{
            NO();
        }
    }
    for(i=1; i<=a; i++){
        cout<<ans[i]<<" ";
    }
    return 0;
}

• Subtask 1: 23 / 23
• Subtask 2: 44 / 44
• Subtask 3: 33 / 33