oj.uz

Submission #791083

# Submission time Handle Problem Language Result Execution time Memory
791083 2023-07-23T11:54:15 Z alexander707070 Comparing Plants (IOI20_plants) C++14
0 / 100
 4000 ms 11372 KB 
#include<bits/stdc++.h>
#define MAXN 200007
using namespace std;

int n,maxs,perm[MAXN];

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 init(int k,vector<int> r){
    n=int(r.size());

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

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

        for(int f=0;f<n;f++){
            if(getmin(1,0,n-1,f,f)==0 and mins(f-k+1,f-1)>0){
                maxs=f;
            }
        }

        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,3,2,0,0,1});
}
*/

Subtask #1
0 / 5.0

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

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 86 ms 436 KB Output is correct
7 Correct 2682 ms 5128 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 88 ms 428 KB Output is correct
10 Correct 2771 ms 5136 KB Output is correct
11 Execution timed out 4050 ms 4732 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 86 ms 436 KB Output is correct
7 Correct 2682 ms 5128 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 88 ms 428 KB Output is correct
10 Correct 2771 ms 5136 KB Output is correct
11 Execution timed out 4050 ms 4732 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 493 ms 4932 KB Output is correct
4 Execution timed out 4048 ms 11372 KB Time limit exceeded
5 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 1 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 1 ms 212 KB Output is correct
3 Incorrect 0 ms 316 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

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