oj.uz

Submission #791097

# Submission time Handle Problem Language Result Execution time Memory
791097 2023-07-23T12:09:51 Z alexander707070 Comparing Plants (IOI20_plants) C++14
27 / 100
 985 ms 12620 KB 
#include<bits/stdc++.h>
#define MAXN 200007
using namespace std;

int n,maxs,perm[MAXN],k;

int tree[4*MAXN],lazy[4*MAXN];

void psh(int v){
    tree[2*v]+=lazy[v];
    tree[2*v+1]+=lazy[v];

    lazy[2*v]+=lazy[v];
    lazy[2*v+1]+=lazy[v];

    lazy[v]=0;
}

void update(int v,int l,int r,int ll,int rr,int val){
    if(ll>rr)return;
    if(l==ll and r==rr){
        tree[v]+=val;
        lazy[v]+=val;
    }else{
        int tt=(l+r)/2;
        psh(v);

        update(2*v,l,tt,ll,min(tt,rr),val);
        update(2*v+1,tt+1,r,max(tt+1,ll),rr,val);
        tree[v]=min(tree[2*v],tree[2*v+1]);
    }
}

int getmin(int v,int l,int r,int ll,int rr){
    if(ll>rr)return n;
    if(l==ll and r==rr){
        return tree[v];
    }else{
        int tt=(l+r)/2;
        psh(v);

        return min( getmin(2*v,l,tt,ll,min(tt,rr)) , getmin(2*v+1,tt+1,r,max(tt+1,ll),rr) );
    }
}

int mins(int l,int r){
    if(l>=0)return getmin(1,0,n-1,l,r);
    return min( getmin(1,0,n-1,n+l,n-1) , getmin(1,0,n-1,0,r) );
}

void upgrade(int l,int r){
    if(l>=0)update(1,0,n-1,l,r,-1);
    else{
        update(1,0,n-1,n+l,n-1,-1);
        update(1,0,n-1,0,r,-1);
    }
}

void solve(int l,int r){

    if(l==r){
        if(mins(l-k+1,l-1)>0)maxs=l;
        return;
    }

    int tt=(l+r)/2;
    if(getmin(1,0,n-1,l,tt)==0){
        solve(l,tt);
    }else if(getmin(1,0,n-1,tt+1,r)==0){
        solve(tt+1,r);
    }
}

void init(int K,vector<int> r){
    n=int(r.size()); k=K;

    for(int i=0;i<n;i++){
        update(1,0,n-1,i,i,r[i]);
    }

    for(int i=n-1;i>=0;i--){

        solve(0,n/2-1);
        solve(n/2,n-1);

        perm[maxs]=i;
        upgrade(maxs-k+1,maxs-1);
        update(1,0,n-1,maxs,maxs,n-1);
    }
}

int compare_plants(int x, int y){
    if(perm[x]>perm[y])return 1;
    return -1;
}

/*
int main(){
    init(4,{3,0,0,0,1,2});
}
*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 0 ms 212 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 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 48 ms 3324 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 50 ms 3324 KB Output is correct
11 Correct 47 ms 3244 KB Output is correct
12 Correct 46 ms 5252 KB Output is correct
13 Correct 57 ms 5192 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 48 ms 3324 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 50 ms 3324 KB Output is correct
11 Correct 47 ms 3244 KB Output is correct
12 Correct 46 ms 5252 KB Output is correct
13 Correct 57 ms 5192 KB Output is correct
14 Correct 125 ms 6032 KB Output is correct
15 Correct 962 ms 12572 KB Output is correct
16 Correct 114 ms 6056 KB Output is correct
17 Correct 985 ms 12576 KB Output is correct
18 Correct 814 ms 12444 KB Output is correct
19 Correct 678 ms 12492 KB Output is correct
20 Correct 827 ms 12620 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

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