oj.uz

Submission #397671

# Submission time Handle Problem Language Result Execution time Memory
397671 2021-05-02T19:19:19 Z Antekb Comparing Plants (IOI20_plants) C++14
14 / 100
 3370 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());

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);
    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;
        b[j+n][j]=1;
        //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";
        }*/
    }
    return;
}
int compare_plants(int x, int y){
	if(b[x+n][y])return 1;
	if(b[y+n][x])return -1;
   	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4560 KB Output is correct
2 Correct 4 ms 4608 KB Output is correct
3 Correct 5 ms 4684 KB Output is correct
4 Incorrect 4 ms 4812 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4556 KB Output is correct
2 Correct 4 ms 4556 KB Output is correct
3 Correct 4 ms 4624 KB Output is correct
4 Correct 4 ms 4824 KB Output is correct
5 Correct 25 ms 10828 KB Output is correct
6 Correct 128 ms 68688 KB Output is correct
7 Correct 852 ms 328176 KB Output is correct
8 Correct 14 ms 10956 KB Output is correct
9 Correct 129 ms 68748 KB Output is correct
10 Correct 859 ms 328320 KB Output is correct
11 Correct 713 ms 328076 KB Output is correct
12 Correct 731 ms 328340 KB Output is correct
13 Correct 859 ms 328324 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4556 KB Output is correct
2 Correct 4 ms 4556 KB Output is correct
3 Correct 4 ms 4624 KB Output is correct
4 Correct 4 ms 4824 KB Output is correct
5 Correct 25 ms 10828 KB Output is correct
6 Correct 128 ms 68688 KB Output is correct
7 Correct 852 ms 328176 KB Output is correct
8 Correct 14 ms 10956 KB Output is correct
9 Correct 129 ms 68748 KB Output is correct
10 Correct 859 ms 328320 KB Output is correct
11 Correct 713 ms 328076 KB Output is correct
12 Correct 731 ms 328340 KB Output is correct
13 Correct 859 ms 328324 KB Output is correct
14 Correct 3370 ms 1291012 KB Output is correct
15 Runtime error 1106 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 Incorrect 4 ms 4684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4556 KB Output is correct
2 Correct 4 ms 4556 KB Output is correct
3 Incorrect 4 ms 4812 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4556 KB Output is correct
2 Correct 4 ms 4552 KB Output is correct
3 Incorrect 4 ms 4684 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4560 KB Output is correct
2 Correct 4 ms 4608 KB Output is correct
3 Correct 5 ms 4684 KB Output is correct
4 Incorrect 4 ms 4812 KB Output isn't correct
5 Halted 0 ms 0 KB -