oj.uz

Submission #397667

# Submission time Handle Problem Language Result Execution time Memory
397667 2021-05-02T19:15:25 Z Antekb Comparing Plants (IOI20_plants) C++14
14 / 100
 3631 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;
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)b[l++]|=c;
        if(r&1)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);
    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][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]|=ans[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(ans[x][y])return 1;
	if(ans[y][x])return -1;
   	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4556 KB Output is correct
2 Correct 4 ms 4684 KB Output is correct
3 Correct 4 ms 4792 KB Output is correct
4 Incorrect 5 ms 5068 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 4688 KB Output is correct
3 Correct 4 ms 4812 KB Output is correct
4 Correct 6 ms 4940 KB Output is correct
5 Correct 15 ms 14160 KB Output is correct
6 Correct 165 ms 100804 KB Output is correct
7 Correct 907 ms 490080 KB Output is correct
8 Correct 16 ms 14156 KB Output is correct
9 Correct 145 ms 100876 KB Output is correct
10 Correct 909 ms 490204 KB Output is correct
11 Correct 770 ms 489924 KB Output is correct
12 Correct 790 ms 490316 KB Output is correct
13 Correct 927 ms 490008 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 4688 KB Output is correct
3 Correct 4 ms 4812 KB Output is correct
4 Correct 6 ms 4940 KB Output is correct
5 Correct 15 ms 14160 KB Output is correct
6 Correct 165 ms 100804 KB Output is correct
7 Correct 907 ms 490080 KB Output is correct
8 Correct 16 ms 14156 KB Output is correct
9 Correct 145 ms 100876 KB Output is correct
10 Correct 909 ms 490204 KB Output is correct
11 Correct 770 ms 489924 KB Output is correct
12 Correct 790 ms 490316 KB Output is correct
13 Correct 927 ms 490008 KB Output is correct
14 Correct 3631 ms 1933836 KB Output is correct
15 Runtime error 1089 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 4940 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 4684 KB Output is correct
2 Correct 4 ms 4684 KB Output is correct
3 Incorrect 4 ms 5068 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 4684 KB Output is correct
3 Incorrect 4 ms 4940 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

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