oj.uz

Submission #397304

# Submission time Handle Problem Language Result Execution time Memory
397304 2021-05-01T21:00:26 Z Antekb Comparing Plants (IOI20_plants) C++14
44 / 100
 1644 ms 16808 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]);
    }
    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);
    }
    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]);
    }
    for(int i=0; i<n; i++){
        //cout<<"a\n";
        check(k, n);
        int j=-ma[1].nd;
        //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 10504 KB Output is correct
2 Correct 8 ms 10444 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 10544 KB Output is correct
2 Correct 8 ms 10444 KB Output is correct
3 Correct 9 ms 10444 KB Output is correct
4 Correct 8 ms 10444 KB Output is correct
5 Correct 9 ms 10444 KB Output is correct
6 Correct 15 ms 10572 KB Output is correct
7 Correct 105 ms 13680 KB Output is correct
8 Correct 11 ms 10632 KB Output is correct
9 Correct 15 ms 10572 KB Output is correct
10 Correct 104 ms 13704 KB Output is correct
11 Correct 95 ms 13560 KB Output is correct
12 Correct 139 ms 13808 KB Output is correct
13 Correct 102 ms 13684 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 10544 KB Output is correct
2 Correct 8 ms 10444 KB Output is correct
3 Correct 9 ms 10444 KB Output is correct
4 Correct 8 ms 10444 KB Output is correct
5 Correct 9 ms 10444 KB Output is correct
6 Correct 15 ms 10572 KB Output is correct
7 Correct 105 ms 13680 KB Output is correct
8 Correct 11 ms 10632 KB Output is correct
9 Correct 15 ms 10572 KB Output is correct
10 Correct 104 ms 13704 KB Output is correct
11 Correct 95 ms 13560 KB Output is correct
12 Correct 139 ms 13808 KB Output is correct
13 Correct 102 ms 13684 KB Output is correct
14 Correct 204 ms 13956 KB Output is correct
15 Correct 1643 ms 16808 KB Output is correct
16 Correct 204 ms 14148 KB Output is correct
17 Correct 1644 ms 16552 KB Output is correct
18 Correct 1136 ms 16528 KB Output is correct
19 Correct 1132 ms 16564 KB Output is correct
20 Correct 1522 ms 16552 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 77 ms 13552 KB Output is correct
4 Correct 803 ms 16324 KB Output is correct
5 Correct 974 ms 16556 KB Output is correct
6 Correct 1240 ms 16580 KB Output is correct
7 Correct 1443 ms 16580 KB Output is correct
8 Correct 1619 ms 16556 KB Output is correct
9 Correct 874 ms 16648 KB Output is correct
10 Correct 893 ms 16472 KB Output is correct
11 Correct 720 ms 16708 KB Output is correct
12 Correct 820 ms 16640 KB Output is correct
13 Correct 1089 ms 16504 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 8 ms 10572 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10444 KB Output is correct
2 Correct 9 ms 10444 KB Output is correct
3 Correct 8 ms 10504 KB Output is correct
4 Incorrect 9 ms 10552 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 10504 KB Output is correct
2 Correct 8 ms 10444 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 -