oj.uz

Submission #397299

# Submission time Handle Problem Language Result Execution time Memory
397299 2021-05-01T20:44:51 Z Antekb Comparing Plants (IOI20_plants) C++14
44 / 100
 871 ms 17348 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);
        assert(ma[1].st>N-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 3 ms 3404 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 #2
14.0 / 14.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 Correct 3 ms 3316 KB Output is correct
4 Correct 3 ms 3404 KB Output is correct
5 Correct 3 ms 3404 KB Output is correct
6 Correct 7 ms 3532 KB Output is correct
7 Correct 83 ms 8388 KB Output is correct
8 Correct 5 ms 3532 KB Output is correct
9 Correct 8 ms 3532 KB Output is correct
10 Correct 80 ms 8296 KB Output is correct
11 Correct 76 ms 8196 KB Output is correct
12 Correct 81 ms 8416 KB Output is correct
13 Correct 84 ms 8388 KB Output is correct

Subtask #3
13.0 / 13.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 Correct 3 ms 3316 KB Output is correct
4 Correct 3 ms 3404 KB Output is correct
5 Correct 3 ms 3404 KB Output is correct
6 Correct 7 ms 3532 KB Output is correct
7 Correct 83 ms 8388 KB Output is correct
8 Correct 5 ms 3532 KB Output is correct
9 Correct 8 ms 3532 KB Output is correct
10 Correct 80 ms 8296 KB Output is correct
11 Correct 76 ms 8196 KB Output is correct
12 Correct 81 ms 8416 KB Output is correct
13 Correct 84 ms 8388 KB Output is correct
14 Correct 133 ms 9344 KB Output is correct
15 Correct 871 ms 16576 KB Output is correct
16 Correct 130 ms 9256 KB Output is correct
17 Correct 853 ms 17340 KB Output is correct
18 Correct 620 ms 16964 KB Output is correct
19 Correct 643 ms 17308 KB Output is correct
20 Correct 805 ms 17348 KB Output is correct

Subtask #4
17.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 Correct 68 ms 8020 KB Output is correct
4 Correct 442 ms 16376 KB Output is correct
5 Correct 543 ms 16696 KB Output is correct
6 Correct 679 ms 16912 KB Output is correct
7 Correct 776 ms 17108 KB Output is correct
8 Correct 847 ms 17304 KB Output is correct
9 Correct 488 ms 16612 KB Output is correct
10 Correct 488 ms 16476 KB Output is correct
11 Correct 397 ms 14956 KB Output is correct
12 Correct 449 ms 16740 KB Output is correct
13 Correct 583 ms 16832 KB Output is correct

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 3408 KB Output is correct
2 Correct 3 ms 3376 KB Output is correct
3 Incorrect 3 ms 3404 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.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 Correct 3 ms 3404 KB Output is correct
4 Incorrect 3 ms 3404 KB Output isn't correct
5 Halted 0 ms 0 KB -