oj.uz

Submission #791082

# Submission time Handle Problem Language Result Execution time Memory
791082 2023-07-23T11:51:12 Z alexander707070 Comparing Plants (IOI20_plants) C++14
0 / 100
 1 ms 308 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;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 308 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 308 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 308 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 308 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

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