Submission #398127

#	Time	Username	Problem	Language	Result	Execution time	Memory
398127		Antekb	Comparing Plants (IOI20_plants)	C++14	25 / 100	1421 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;

vector<bitset<N> > b;
vector<bool> czy;
int n;
/*void addbit(int l, int r, bitset<N> c){
    r++;
    for(l+=n, r+=n; l<r; l>>=1, r>>=1){
        if(l&1){
            if(czy[l])b[l]|=c;
            l++;
        }
        if(r&1){
            --r;
            if(czy[r])b[r]|=c;
        }
    }
}
void comp(int x){
    if(x==1)return;
    comp(x/2);
    b[x]|=b[x/2];
}*/
//vector<bitset<N>> ans;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

pair<int, int> H[2*N];
typedef pair<int, int> pii;
pii getmin(int l, int r){
    r++;
    pii ans=mp(0, 0);
    for(l+=N, r+=N; l<r; l>>=1, r>>=1){
        if(l&1)ans=max(ans, H[l++]);
        if(r&1)ans=max(ans, H[--r]);
    }
    return ans;
}
void ust(int i, pii val){
    for(i+=N, H[i]=val, i>>=1; i>0; i>>=1){
        H[i]=max(H[i+i], H[i+i+1]);
    }
}
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(n);
    //czy.resize(2*n, 1);
    //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);
        //czy[j+n]=0;
    	V[j]=i;
        //ans[j]=b[j+n];  
        //assert(ans[j].count()==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[n-u.nd]|=b[j+n];
            //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, b[j+n]);
            //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, b[j+n]);
            //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";
        }*/
    }
    for(int i=0; i<n; i++){
        H[N+S[i]]=mp(N-i, S[i]);
    }
    for(int i=N-1; i>0; i--){
        H[i]=max(H[i+i], H[i+i+1]);
    }
    for(int j:S){
        //cout<<j<<"\n";
        b[j][j]=1;
        pii u=mp(0, 0);

        if(j<n-1)u=max(u, getmin(j+1, min(j+k, n-1)));
        if(j+k>=n)u=max(u, getmin(0, j+k-n));
        //cout<<u.st<<" "<<u.nd<<"\n";
        if(u.st>0)b[u.nd]|=b[j];
        u=mp(0, 0);
        if(j)u=max(u, getmin(max(j-k, 0), j-1));
        if(j-k<0)u=max(u, getmin(n+j-k, n-1));
        if(u.st>0)b[u.nd]|=b[j];
        ust(j, mp(0, 0));
    }
    return;
}
int compare_plants(int x, int y){
	if(b[x][y])return 1;
	if(b[y][x])return -1;
   	return 0;
}

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