oj.uz

Submission #398127

# Submission time Handle Problem Language Result Execution time Memory
398127 2021-05-03T18:15:13 Z Antekb Comparing Plants (IOI20_plants) C++14
25 / 100
 1421 ms 2097156 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6476 KB Output is correct
2 Correct 5 ms 6476 KB Output is correct
3 Correct 5 ms 6604 KB Output is correct
4 Correct 6 ms 6640 KB Output is correct
5 Correct 5 ms 6732 KB Output is correct
6 Correct 86 ms 10820 KB Output is correct
7 Correct 544 ms 653672 KB Output is correct
8 Runtime error 1421 ms 2097156 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6476 KB Output is correct
2 Correct 6 ms 6604 KB Output is correct
3 Correct 6 ms 6604 KB Output is correct
4 Correct 6 ms 6604 KB Output is correct
5 Correct 9 ms 9664 KB Output is correct
6 Correct 39 ms 38732 KB Output is correct
7 Correct 220 ms 171844 KB Output is correct
8 Correct 10 ms 9928 KB Output is correct
9 Correct 35 ms 38732 KB Output is correct
10 Correct 223 ms 171824 KB Output is correct
11 Correct 209 ms 171812 KB Output is correct
12 Correct 237 ms 171972 KB Output is correct
13 Correct 218 ms 172024 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6476 KB Output is correct
2 Correct 6 ms 6604 KB Output is correct
3 Correct 6 ms 6604 KB Output is correct
4 Correct 6 ms 6604 KB Output is correct
5 Correct 9 ms 9664 KB Output is correct
6 Correct 39 ms 38732 KB Output is correct
7 Correct 220 ms 171844 KB Output is correct
8 Correct 10 ms 9928 KB Output is correct
9 Correct 35 ms 38732 KB Output is correct
10 Correct 223 ms 171824 KB Output is correct
11 Correct 209 ms 171812 KB Output is correct
12 Correct 237 ms 171972 KB Output is correct
13 Correct 218 ms 172024 KB Output is correct
14 Correct 711 ms 653928 KB Output is correct
15 Runtime error 1082 ms 2097156 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6604 KB Output is correct
2 Correct 6 ms 7132 KB Output is correct
3 Correct 125 ms 75324 KB Output is correct
4 Runtime error 1034 ms 2097156 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6476 KB Output is correct
2 Correct 6 ms 6476 KB Output is correct
3 Correct 6 ms 6604 KB Output is correct
4 Correct 7 ms 6676 KB Output is correct
5 Correct 7 ms 7452 KB Output is correct
6 Correct 11 ms 9808 KB Output is correct
7 Correct 28 ms 16996 KB Output is correct
8 Correct 28 ms 17056 KB Output is correct
9 Correct 28 ms 17096 KB Output is correct
10 Correct 28 ms 17104 KB Output is correct
11 Correct 27 ms 17100 KB Output is correct
12 Correct 28 ms 17092 KB Output is correct
13 Correct 28 ms 17092 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6476 KB Output is correct
2 Correct 7 ms 6476 KB Output is correct
3 Correct 6 ms 6592 KB Output is correct
4 Correct 9 ms 6780 KB Output is correct
5 Correct 34 ms 38696 KB Output is correct
6 Runtime error 1030 ms 2097156 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6476 KB Output is correct
2 Correct 5 ms 6476 KB Output is correct
3 Correct 5 ms 6604 KB Output is correct
4 Correct 6 ms 6640 KB Output is correct
5 Correct 5 ms 6732 KB Output is correct
6 Correct 86 ms 10820 KB Output is correct
7 Correct 544 ms 653672 KB Output is correct
8 Runtime error 1421 ms 2097156 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -