제출 #397666

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
397666		Antekb	식물 비교 (IOI20_plants)	C++14	11 / 100	4208 ms	2097156 KiB

plants

#include "plants.h"
#include<bits/stdc++.h>
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)
#define st first
#define nd second
using namespace std;
const int N=(1<<18);
int lazy[2*N];
pair<int, int> maks[2*N];
void prop1(int v){
    if(!lazy[v] || v>N)return;
    int l=2*v, r=l+1;
    lazy[l]+=lazy[v];
    lazy[r]+=lazy[v];
    maks[l].st+=lazy[v];
    maks[r].st+=lazy[v];
    lazy[v]=0;
}
void add(int v, int l, int r ,int L, int R, int c){
    //if(v==1)cout<<"a"<<l<<" "<<r<<" "<<c<<"\n";
    //cout<<v<<" "<<l<<" "<<r<<" "<<L<<" "<<R<<"\n";
    if(l==L && r==R){
        lazy[v]+=c;
        maks[v].st+=c;
        return;
    }
    prop1(v);
    int M=(L+R)>>1;
    if(l<=M)add(2*v, l, min(M, r), L, M, c);
    if(r>M)add(2*v+1, max(M+1, l), r, M+1, R, c);
    maks[v]=max(maks[2*v], maks[2*v+1]);
    return;
}
pair<int, int> quer1(int v, int l, int r, int L, int R){
    if(l==L && r==R){
        return maks[v];
    }
    int M=(L+R)>>1;
    prop1(v);
    pair<int, int> ans=mp(0, 0);
    if(l<=M)ans=max(ans, quer1(2*v, l, min(M, r), L, M));
    if(r>M)ans=max(ans, quer1(2*v+1, max(M+1, l), r, M+1, R));
    return ans;
}
int lazy2[2*N];
pair<int, int> ma[2*N];
void prop2(int v){
    if(!lazy2[v] || v>N)return;
    int l=2*v, r=l+1;
    lazy2[l]+=lazy2[v];
    lazy2[r]+=lazy2[v];
    ma[l].st+=lazy2[v];
    ma[r].st+=lazy2[v];
    lazy2[v]=0;
}
void add2(int v, int l, int r ,int L, int R, int c){
    //if(v==1)cout<<"b"<<l<<" "<<r<<" "<<c<<"\n";
    //cout<<"c"<<"\n";
    if(l==L && r==R){
        lazy2[v]+=c;
        ma[v].st+=c;
        return;
    }
    prop2(v);
    int M=(L+R)>>1;
    if(l<=M)add2(2*v, l, min(M, r), L, M, c);
    if(r>M)add2(2*v+1, max(M+1, l), r, M+1, R, c);
    ma[v]=max(ma[2*v], ma[2*v+1]);
    return;
}
pair<int, int> quer2(int v, int l, int r, int L, int R){
    if(l==L && r==R){
        return ma[v];
    }
    int M=(L+R)>>1;
    prop2(v);
    pair<int, int> ans=mp(0, 0);
    if(l<=M)ans=max(ans, quer2(2*v, l, min(M, r), L, M));
    if(r>M)ans=max(ans, quer2(2*v+1, max(M+1, l), r, M+1, R));
    return ans;
}
void check(int k, int n){
    while(maks[1].st==k){
        //cout<<"b\n";
        int v=1;
        while(v<N){
            prop1(v);
            if(maks[2*v].st==k)v*=2;
            else v=2*v+1;
        }
        add(1, v-N, v-N, 0, N-1, -N);
        add2(1, v-N, v-N, 0, N-1, N);
        if(v-N<n-1)add2(1, v-N+1, min(v-N+k, n-1), 0, N-1, -1);
        if(v-N+k>=n)add2(1, 0, v-N+k-n, 0, N-1, -1);
    }
}
vector<int> V, V2;
struct node{
    node* l=nullptr, *r=nullptr;
    int sum;
    void upd(){
        sum=0;
        if(l)sum+=l->sum;
        if(r)sum+=r->sum;
    }
    node(node* _l, node* _r) : l(_l), r(_r) {sum=1;}
};
node* left(node* v){if(!v)return nullptr; return v->l;}
node* right(node* v){if(!v)return nullptr; return v->r;}
node* add(node* v, int L, int R, int id){
    if(L==R){
        return new node(0, 0);
    }
    int M=(L+R)>>1;
    node* u=new node(left(v), right(v));
    if(id<=M)u->l=add(left(v), L, M, id);
    else u->r=add(right(v), M+1, R, id);
    u->upd();
    return u;
}
node* merge(node* u, node* v){
    if(!u)return v;
    if(!v)return u;
    node* w=new node(merge(left(u), left(v)), merge(right(u), right(v)));
    w->upd();
    return w;
}
bool czy(node* v, int L, int R, int id){
    if(!v)return 0;
    if(L==R)return 1;
    int M=(L+R)>>1;
    if(id<=M)return czy(left(v), L, M, id);
    else return czy(right(v), M+1, R, id);
}
vector<node* > b;
int n;
void addbit(int l, int r, node* c){
    r++;
    for(l+=n, r+=n; l<r; l>>=1, r>>=1){
        if(l&1)b[l]=merge(b[l], c), l++;
        if(r&1)r--, b[r]=merge(b[r], c);
    }
}
void comp(int x){
    if(x==1)return;
    comp(x/2);
    b[x]=merge(b[x/2], b[x]);
}
vector<node*> ans;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

void init(int k, std::vector<int> r) {
    /*b.clear();
    ans.clear();
    V.clear();
    for(int i=0; i<2*N; i++)maks[i]=ma[i]=mp(0, 0), lazy[i]=lazy2[i]=0;
    vector<int> perm(r.size());
    iota(perm.begin(), perm.end(), 0);
    shuffle(perm.begin(), perm.end(), rng);
    for(int i=0; i<r.size(); i++){
        cout<<perm[i];
        r[i]=0;
        for(int j=1; j<k; j++){
            r[i]+=(perm[i]>perm[(i+j)%r.size()]);
        }
    }
    cout<<"\n";
    for(int i=0; i<r.size(); i++)cout<<r[i]<<" ";
        cout<<"\n";*/
    n=r.size();
    k--;
    V.resize(n);
    for(int i=0; i<n; i++){
        ma[N+i].nd=-i;
        maks[N+i].st=r[i];
        maks[N+i].nd=-i;
    }
    for(int i=N-1; i>0; i--){
        ma[i]=max(ma[2*i], ma[2*i+1]);
        maks[i]=max(maks[2*i], maks[2*i+1]);
    }
    vector<int> S;
    b.resize(2*n);
    ans.resize(n);
    for(int i=0; i<n; i++){
        //cout<<"a\n";
        check(k, n);
    	while(ma[1].st==N){
            S.push_back(-ma[1].nd);
            add2(1, -ma[1].nd, -ma[1].nd, 0, N-1, -N);
            //cout<<"+";
        }
        int j=S[i];
        //cout<<j<<"\n";
        comp(j+n);
    	V[j]=i;
        b[j+n]=add(b[j+n], 0, N-1, j);
        ans[j]=b[j+n];
        //assert(ans[j]->sum==i+1);
        //for(int l=0; l<n; l++)cout<<ans[j][l];cout<<"\n";
        pair<int, int> u=mp(0,0);
        if(j<n-1){
            add2(1, j+1, min(j+k, n-1), 0, N-1, 1);
            addbit(j+1, min(j+k, n-1), ans[j]);
            //u=max(u, quer2(1, j+1, min(j+k, n-1), 0, N-1));
        }
        if(j+k>=n){
            add2(1, 0, j+k-n, 0, N-1, 1);
            addbit(0, j+k-n, ans[j]);
            //u=max(u, quer2(1, 0, j+k-n, 0, N-1));
        }
        /*if(u.st==N){
            b[-u.nd]|=b[j];
            cout<<-u.nd<<"x\n";
        }*/
        u=mp(0, 0);
    	if(j){
            add(1, max(j-k, 0), j-1, 0, N-1, 1);
            addbit(max(j-k, 0), j-1, ans[j]);
            //u=max(u, quer1(1, max(j-k, 0), j-1, 0, N-1));
        }
        if(j-k<0){
            add(1, n+j-k, n-1, 0, N-1, 1);
            addbit(n+j-k, n-1, ans[j]);
            //u=max(u, quer1(1, n+j-k, n-1, 0, N-1));
        }
        /*if(u.st==k){
            b[-u.nd]|=b[j];
            cout<<-u.nd<<"y\n";
        }*/
    }
    return;
}
int compare_plants(int x, int y){
	if(czy(ans[x], 0, N-1, y))return 1;
	if(czy(ans[y], 0, N-1, x))return -1;
   	return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 11 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25