QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#618188	#2559. Endless Road	fzx	TL	11ms	138820kb	C++14	6.6kb	2024-10-06 19:38:27	2024-10-06 19:38:29

Judging History

你现在查看的是最新测评结果

[2024-10-06 19:38:29]
评测

测评结果：TL
用时：11ms
内存：138820kb

查看

[2024-10-06 19:38:27]
提交

answer

#include <bits/stdc++.h>
#define int long long 
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int INF=1e6+5;

struct P3{
    int l,r,id;
}aa[INF];
int n,ll[INF],rr[INF],pre[INF];
pii A[INF]; 
// A 维护合法的左端点
vector <int> cnt;
set <int> s3;

set < pii > s; // s 集合维护所有合法的区间
struct P2{
    int l,id;
    bool operator < (const P2 &x) const {
        if (x.l!=l) return x.l>l;
        else return x.id<id;
    }
};
set <P2> s2[INF];
int Get(int x) {return lower_bound(cnt.begin(),cnt.end(),x)-cnt.begin()+1;}
struct BIT{
    int tree[INF];
    void add(int x,int y) {for (int i=x;i<=1e6;i+=i&-i) tree[i]+=y;}
    int query(int x) {int sum=0;for (int i=x;i;i-=i&-i) sum+=tree[i];return sum;}
}T1;
struct Segment{
    #define ll tl[id]
    #define rr tr[id]
    #define ls(x) x<<1
    #define rs(x) x<<1|1
    int tl[INF<<2],tr[INF<<2],lazy[INF<<2];
    pii sum[INF<<2];int sum2[INF<<2];
    void push_up(int id) {
        sum[id]=min(sum[ls(id)],sum[rs(id)]);
        sum2[id]=min(sum2[ls(id)],sum2[rs(id)]);
    }
    void push_down(int id) {
        if (!lazy[id]) return ;
        int rt=ls(id),x=lazy[id];
        sum[rt].fi+=x;lazy[rt]+=x;
        rt=rs(id),x=lazy[id];
        sum[rt].fi+=x;lazy[rt]+=x;
        lazy[id]=0;
    }
    void build(int l,int r,int id) {
        ll=l;rr=r;
        if (ll==rr) {
            int N=1e18;
            if (A[ll].se) 
                sum[id]={cnt[ll-1]-A[ll].fi,A[ll].se},
                sum2[id]=aa[pre[A[ll].se]].l;
            else sum[id]={N,0},sum2[id]=-N;
            return ;
        }
        int Mid=(ll+rr)>>1;
        build(ll,Mid,ls(id));
        build(Mid+1,rr,rs(id));
        push_up(id);
    }
    void add(int l,int id) {
        if (ll==rr) {
            int N=1e18;
            if (A[ll].se) 
                sum[id]={A[ll].fi,A[ll].se},
                sum2[id]=aa[pre[A[ll].se]].l;
            else sum[id]={N,0},sum2[id]=-N;
            return ;
        }
        push_down(id);
        int Mid=(ll+rr)>>1;
        if (l<=Mid) add(l,ls(id));
        else add(l,rs(id));
        push_up(id);
//        cerr<<ll<<" "<<rr<<" "<<sum[id].fi<<" "<<sum[id].se<<" qaqqwq?\n";
    }
    void add2(int l,int r,int x,int id) {
        if (l<=ll && rr<=r) {
            sum[id].fi+=x;
            lazy[id]+=x;
            return ;
        }
        push_down(id);
        int Mid=(ll+rr)>>1;
        if (l<=Mid) add2(l,r,x,ls(id));
        if (Mid<r) add2(l,r,x,rs(id));
        push_up(id);
    }
    int query2(int l,int L,int id) {
        if (rr<l) return -1;
//        cerr<<sum2[id]<<" "<<L<<" "<<rr<<" "<<l<<" "<<id<<" qweiorj!!!!!!!!!!!!!!!!!!!!!!!!1\n";
        if (sum2[id]>=L) return -1;
        if (ll==rr) return ll;
        push_down(id);
        int ba=query2(l,L,rs(id));
        if (ba==-1) ba=query2(l,L,ls(id)); 
        return ba;
    }
    #undef ll
    #undef rr
    #undef ls
    #undef rs
}T2;
struct Segment2{
    #define ll tl[id]
    #define rr tr[id]
    #define ls(x) x<<1
    #define rs(x) x<<1|1
    int tl[INF<<2],tr[INF<<2],sum[INF<<2];
    void push_up(int id) {sum[id]=max(sum[ls(id)],sum[rs(id)]);}
    void build(int l,int r,int id) {
        ll=l;rr=r;
        if (ll==rr) {if (s2[ll].size()) sum[id]=s2[ll].begin()->l;else sum[id]=-1e18;return ;}
        int Mid=(ll+rr)>>1;
        build(ll,Mid,ls(id));
        build(Mid+1,rr,rs(id));
        push_up(id);
    }
    void add(int l,int id) {
        if (ll==rr) {
            if (s2[ll].size()) sum[id]=s2[ll].begin()->l;
            else sum[id]=-1e18;
            return ;
        }
        int Mid=(ll+rr)>>1;
        if (l<=Mid) add(l,ls(id));
        else add(l,rs(id));
        push_up(id);
    }
    int query(int l,int L,int id) {
        if (rr<l) return -1;
        if (sum[id]<L) return -1;
        if (ll==rr) return ll;
        int ba=query(l,L,ls(id));
        if (ba==-1) ba=query(l,L,rs(id)); 
        return ba;
    }
    #undef ll
    #undef rr
    #undef ls
    #undef rs
}T3;
void del(int x) {
    // [cnt[x-2],cnt[x-1]]
    int T=T2.query2(x,cnt[x-1],1);
//    cerr<<cnt[x-2]<<" "<<cnt[x-1]<<" "<<x-1<<" "<<T<<" "<<aa[pre[A[x].se]].l<<" qaqqwq?\n";
    if (T!=-1) {T2.add2(x,T,-(cnt[x-1]-cnt[x-2]),1);}
}
signed main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for (int i=1;i<=n;i++) 
        cin>>ll[i]>>rr[i],cnt.pb(ll[i]),cnt.pb(rr[i]);
    sort(cnt.begin(),cnt.end());
    cnt.erase(unique(cnt.begin(),cnt.end()),cnt.end());
    for (int i=1;i<=n;i++) aa[i]={ll[i],rr[i],i};
    sort(aa+1,aa+1+n,[](P3 xx,P3 yy){return xx.r!=yy.r?xx.r<yy.r:(xx.l!=yy.l?xx.l>yy.l:xx.id<yy.id);});
    int L=-1;
    for (int i=1;i<=n;i++) {
        if (aa[i].l<=L) s2[Get(aa[i].r)].insert({aa[i].l,aa[i].id});
        else L=max(L,aa[i].l),A[Get(aa[i].r)]={aa[i].l,aa[i].id},s.insert({aa[i].l,aa[i].r});
    }
    for (int i=1;i<=n;i++) pre[aa[i].id]=i;
    int len=cnt.size();
    for (int i=1;i<=len;i++) s3.insert(i);
    T2.build(1,len,1);int T=n;
    T3.build(1,len,1);
    
//    cerr<<len<<"\n";
//    for (int i=1;i<=len;i++) cerr<<cnt[i-1]<<" ";
//    cerr<<" endl\n";
//    T=5; // ATTTTT!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
    while (T--) {
        int id=T2.sum[1].se;
        cout<<id<<" ";
        id=pre[id];
        // aa[id].l aa[id].r
        int it2=Get(aa[id].l)+1,it3=Get(aa[id].r);
        auto I=s3.lower_bound(it2);
        auto I2=s.lower_bound({aa[id].l,aa[id].r});
        vector <int> cnt5;
        for (auto it=I;it!=s3.end();it++) {
            if (*it>it3) break;cnt5.pb(*it);
        }
        for (int i:cnt5) {
            del(i),s3.erase(i),T1.add(i,cnt[i-1]-cnt[i-2]);
//        	cerr<<i<<" "<<cnt[i-1]-cnt[i-2]<<" iroweqj\n";
		}
        int LL=-1;
        if (I2!=s.begin()) {
            auto Ij2=I2;Ij2--;
            LL=Get(Ij2->fi);
        }
        int RR=len+1;
        auto Is=I2;Is++;
        if (Is!=s.end()) RR=Get(Is->se);
		A[it3]={0,0};
		T2.add(it3,1);
        int la=it3;
        while (la<RR) {
            int F=T3.query(la,LL,1);
            if (F==-1) break;
            if (F>=RR) break;
//            cerr<<F<<" "<<cnt[F-1]<<" "<<RR<<" "<<s.size()<<" qweorji\n";
            la=F+1;auto it5=*(--s2[F].end());
			s2[F].erase(--s2[F].end());s.insert({aa[pre[it5.id]].l,aa[pre[it5.id]].r});
//            cerr<<F<<" "<<cnt[F-1]-it5.l-(T1.query(F)-T1.query(Get(it5.l)))<<" "<<it5.id<<" bomb?\n";
			T3.add(F,1);A[F]={cnt[F-1]-it5.l-(T1.query(F)-T1.query(Get(it5.l))),it5.id};
			T2.add(F,1);
        }        
        s.erase(I2);
    }
    cout<<"\n";
    return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 8ms

memory: 138804kb

input:

output:

1 2 5 3 4 6

result:

ok 6 tokens

Test #2:

score: 0

Accepted

time: 11ms

memory: 138820kb

input:

output:

1 3 2 4

result:

ok 4 tokens

Test #3:

score: -100

Time Limit Exceeded

input: