oj.uz

Submission #397280

# Submission time Handle Problem Language Result Execution time Memory
397280 2021-05-01T19:34:09 Z Antekb Comparing Plants (IOI20_plants) C++14
0 / 100
 70 ms 6504 KB 
#include "plants.h"
#include<bits/stdc++.h>
#define pb(x) push_back(x)
#define st first
#define nd second
using namespace std;
const int N=(1<<18);
int lazy[2*N], 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]+=lazy[v];
    maks[r]+=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]+=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;
}
int lazy2[2*N];
pair<int, int> ma[2*N];
void prop2(int v){
    if(!lazy[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];
    lazy[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;
}
void check(int k, int n){
    while(maks[1]==k){
        //cout<<"b\n";
        int v=1;
        while(v<N){
            if(maks[2*v]==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;
void init(int k, std::vector<int> r) {
    int n=r.size();
    k--;
    V.resize(n);
    for(int i=0; i<n; i++){
        ma[N+i].nd=i;
        maks[N+i]=r[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]);
    }
    for(int i=0; i<n; i++){
        //cout<<"a\n";
        check(k, n);
    	int j=ma[1].nd;
        //cout<<j<<"\n";
    	V[j]=i;
    	add2(1, j, j, 0, N-1, -N);
        if(j<n-1)add2(1, j+1, min(j+k, n-1), 0, N-1, 1);
        if(j+k>=n)add2(1, 0, j+k-n, 0, N-1, 1);
    	if(j)add(1, max(j-k, 0), j-1, 0, N-1, 1);
        if(j-k<0)add(1, n+j-k, n-1, 0, N-1, 1);
    }
	return;
}     
int compare_plants(int x, int y){
	if(V[x]<V[y])return -1;
	if(V[x]>V[y])return 1;
   	return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3292 KB Output is correct
2 Correct 3 ms 3404 KB Output is correct
3 Incorrect 3 ms 3276 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 3276 KB Output is correct
2 Correct 3 ms 3276 KB Output is correct
3 Correct 3 ms 3276 KB Output is correct
4 Incorrect 3 ms 3388 KB Output isn't correct
5 Halted 0 ms 0 KB -