oj.uz

Submission #397647

# Submission time Handle Problem Language Result Execution time Memory
397647 2021-05-02T18:17:29 Z Antekb Comparing Plants (IOI20_plants) C++14
0 / 100
 1856 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){
    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)comp(x/2);
    b[x]|=b[x/2];
}
vector<bitset<N>> ans;
void init(int k, std::vector<int> r) {
    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];  
        //cout<<ans[j][0]<<" "<<ans[j][1]<<" "<<ans[j][2]<<" "<<ans[j][3]<<"\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)+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+1, 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, 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, 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 4812 KB Output is correct
4 Correct 5 ms 5068 KB Output is correct
5 Correct 5 ms 5324 KB Output is correct
6 Correct 65 ms 10076 KB Output is correct
7 Correct 1856 ms 1934016 KB Output is correct
8 Runtime error 1096 ms 2097156 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4636 KB Output is correct
2 Correct 4 ms 4684 KB Output is correct
3 Correct 4 ms 4812 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Incorrect 17 ms 14156 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4636 KB Output is correct
2 Correct 4 ms 4684 KB Output is correct
3 Correct 4 ms 4812 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Incorrect 17 ms 14156 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4960 KB Output is correct
2 Incorrect 6 ms 6348 KB Output isn't correct
3 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 4684 KB Output is correct
3 Correct 4 ms 4944 KB Output is correct
4 Correct 5 ms 5068 KB Output is correct
5 Correct 6 ms 7332 KB Output is correct
6 Incorrect 14 ms 14156 KB Output isn't correct
7 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 5 ms 4684 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 5 ms 5456 KB Output is correct
5 Incorrect 138 ms 100848 KB Output isn't correct
6 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 4812 KB Output is correct
4 Correct 5 ms 5068 KB Output is correct
5 Correct 5 ms 5324 KB Output is correct
6 Correct 65 ms 10076 KB Output is correct
7 Correct 1856 ms 1934016 KB Output is correct
8 Runtime error 1096 ms 2097156 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -