oj.uz

Submission #397311

# Submission time Handle Problem Language Result Execution time Memory
397311 2021-05-01T21:15:32 Z Antekb Comparing Plants (IOI20_plants) C++14
44 / 100
 1860 ms 18048 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(!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;
}
void check(int k, int n){
    while(maks[1]==k){
        //cout<<"b\n";
        int v=1;
        while(v<N){
            prop1(v);
            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]);
    }
    stack<int> S;
    for(int i=0; i<n; i++){
        //cout<<"a\n";
        check(k, n);
    	while(ma[1].st==N){
            S.push(ma[1].nd);
            add2(1, ma[1].nd, ma[1].nd, 0, N-1, -N);
        }
        int j=S.top();
        S.pop();
        //cout<<j<<"\n";
    	V[j]=i;
        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);
    }
    V2.resize(n);
    for(int i=0; i<2*N; i++){
        ma[i]=make_pair(0, 0);
        maks[i]=0;
        lazy[i]=0;
        lazy2[i]=0;
    }
    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]);
    }
    queue<int> Q;
    for(int i=0; i<n; i++){
        //cout<<"a\n";
        check(k, n);
        while(ma[1].st==N){
            Q.push(ma[1].nd);
            add2(1, ma[1].nd, ma[1].nd, 0, N-1, -N);
        }
        int j=Q.front();
        Q.pop();
        //cout<<j<<"\n";
        V2[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] && V2[x]<V2[y])return -1;
	if(V[x]>V[y] && V2[x]>V2[y])return 1;
   	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10444 KB Output is correct
2 Correct 8 ms 10552 KB Output is correct
3 Correct 8 ms 10444 KB Output is correct
4 Incorrect 8 ms 10444 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 9 ms 10444 KB Output is correct
2 Correct 8 ms 10556 KB Output is correct
3 Correct 8 ms 10444 KB Output is correct
4 Correct 8 ms 10536 KB Output is correct
5 Correct 9 ms 10444 KB Output is correct
6 Correct 16 ms 10640 KB Output is correct
7 Correct 107 ms 14200 KB Output is correct
8 Correct 10 ms 10552 KB Output is correct
9 Correct 19 ms 10572 KB Output is correct
10 Correct 108 ms 14148 KB Output is correct
11 Correct 97 ms 14060 KB Output is correct
12 Correct 96 ms 14256 KB Output is correct
13 Correct 106 ms 14276 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 10444 KB Output is correct
2 Correct 8 ms 10556 KB Output is correct
3 Correct 8 ms 10444 KB Output is correct
4 Correct 8 ms 10536 KB Output is correct
5 Correct 9 ms 10444 KB Output is correct
6 Correct 16 ms 10640 KB Output is correct
7 Correct 107 ms 14200 KB Output is correct
8 Correct 10 ms 10552 KB Output is correct
9 Correct 19 ms 10572 KB Output is correct
10 Correct 108 ms 14148 KB Output is correct
11 Correct 97 ms 14060 KB Output is correct
12 Correct 96 ms 14256 KB Output is correct
13 Correct 106 ms 14276 KB Output is correct
14 Correct 211 ms 14440 KB Output is correct
15 Correct 1860 ms 17268 KB Output is correct
16 Correct 226 ms 15524 KB Output is correct
17 Correct 1747 ms 17852 KB Output is correct
18 Correct 1264 ms 18048 KB Output is correct
19 Correct 1187 ms 17988 KB Output is correct
20 Correct 1614 ms 17848 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10444 KB Output is correct
2 Correct 8 ms 10444 KB Output is correct
3 Correct 91 ms 14048 KB Output is correct
4 Correct 866 ms 16808 KB Output is correct
5 Correct 1078 ms 17868 KB Output is correct
6 Correct 1381 ms 17976 KB Output is correct
7 Correct 1556 ms 17960 KB Output is correct
8 Correct 1716 ms 17964 KB Output is correct
9 Correct 1039 ms 17996 KB Output is correct
10 Correct 1008 ms 17860 KB Output is correct
11 Correct 770 ms 17928 KB Output is correct
12 Correct 874 ms 17960 KB Output is correct
13 Correct 1156 ms 17888 KB Output is correct

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 10548 KB Output is correct
2 Correct 8 ms 10460 KB Output is correct
3 Correct 8 ms 10444 KB Output is correct
4 Incorrect 8 ms 10504 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

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