oj.uz

Submission #997657

# Submission time Handle Problem Language Result Execution time Memory
997657 2024-06-12T16:29:50 Z bachhoangxuan Comparing Plants (IOI20_plants) C++17
44 / 100
 212 ms 22532 KB 
#include "plants.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;
const int inf = 1e9;
int n,k;
vector<int> P,R;
set<int> ss,cc;

void cal(int x,int y){
    cc.erase(y);
    if((y-x+n)%n>=k){
        //cout << "add " << y << '\n';
        cc.insert(y);
    }
}

void add(int x){
    if(ss.empty()){
        ss.insert(x);
        cc.insert(x);
        //cout << "add " << x << '\n';
        return;
    }
    auto it=ss.lower_bound(x);
    if(it!=ss.end()) cal(x,*it);
    else cal(x,*ss.begin());
    if(it==ss.begin()) cal(*ss.rbegin(),x);
    else{
        it--;
        cal(*it,x);
    }
    ss.insert(x);
}
void del(int x){
    cc.erase(x);ss.erase(x);
    if(ss.empty()) return;
    auto it=ss.lower_bound(x);
    int y=(it!=ss.end()?*it:*ss.begin());
    cc.insert(y);
}

int tree[4*maxn],lazy[4*maxn];
void build(int l,int r,int id){
    if(l==r){
        tree[id]=R[l];
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,id<<1);build(mid+1,r,id<<1|1);
    tree[id]=min(tree[id<<1],tree[id<<1|1]);
}
void getnew(int id,int val){
    tree[id]-=val;
    lazy[id]+=val;
}
void pushdown(int id){
    if(!lazy[id]) return;
    getnew(id<<1,lazy[id]);
    getnew(id<<1|1,lazy[id]);
    lazy[id]=0;
}
void get(int l,int r,int id){
    if(tree[id]>0) return;
    if(l==r){
        tree[id]=inf;
        //cout << "add2 " << l << '\n';
        add(l);
        return;
    }
    pushdown(id);
    int mid=(l+r)>>1;
    get(l,mid,id<<1);get(mid+1,r,id<<1|1);
    tree[id]=min(tree[id<<1],tree[id<<1|1]);
}
void update(int l,int r,int id,int tl,int tr){
    if(tr<l || r<tl) return;
    if(tl<=l && r<=tr){
        getnew(id,1);
        return;
    }
    pushdown(id);
    int mid=(l+r)>>1;
    update(l,mid,id<<1,tl,tr);update(mid+1,r,id<<1|1,tl,tr);
    tree[id]=min(tree[id<<1],tree[id<<1|1]);
}

void init(int _k, std::vector<int> r) {
    k=_k;R=r;
    n=(int)r.size();
    P.assign(n,0);
    build(0,n-1,1);
    for(int i=n-1;i>=0;i--){
        get(0,n-1,1);
        int x=*cc.begin();P[x]=i;del(x);
        //cout << "P " << x << ' ' << i << '\n';
        if(x>=k-1) update(0,n-1,1,x-k+1,x);
        else{
            update(0,n-1,1,0,x);
            update(0,n-1,1,n-(k-x)+1,n-1);
        }
    }
    //for(int i=0;i<n;i++) cout << P[i] << ' ';
    //cout << '\n';
}

int compare_plants(int x, int y) {
	return (P[x]>P[y]?1:-1);
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Incorrect 1 ms 2396 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 0 ms 2396 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 35 ms 7156 KB Output is correct
8 Correct 2 ms 2392 KB Output is correct
9 Correct 2 ms 2396 KB Output is correct
10 Correct 35 ms 7260 KB Output is correct
11 Correct 34 ms 7168 KB Output is correct
12 Correct 32 ms 7512 KB Output is correct
13 Correct 34 ms 7252 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 35 ms 7156 KB Output is correct
8 Correct 2 ms 2392 KB Output is correct
9 Correct 2 ms 2396 KB Output is correct
10 Correct 35 ms 7260 KB Output is correct
11 Correct 34 ms 7168 KB Output is correct
12 Correct 32 ms 7512 KB Output is correct
13 Correct 34 ms 7252 KB Output is correct
14 Correct 47 ms 10068 KB Output is correct
15 Correct 186 ms 14420 KB Output is correct
16 Correct 46 ms 9976 KB Output is correct
17 Correct 183 ms 14420 KB Output is correct
18 Correct 180 ms 18768 KB Output is correct
19 Correct 134 ms 14672 KB Output is correct
20 Correct 182 ms 14672 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 32 ms 7144 KB Output is correct
4 Correct 142 ms 16704 KB Output is correct
5 Correct 163 ms 14716 KB Output is correct
6 Correct 212 ms 14284 KB Output is correct
7 Correct 197 ms 14416 KB Output is correct
8 Correct 195 ms 14424 KB Output is correct
9 Correct 174 ms 16212 KB Output is correct
10 Correct 165 ms 14512 KB Output is correct
11 Correct 151 ms 22532 KB Output is correct
12 Correct 133 ms 13908 KB Output is correct
13 Correct 182 ms 20600 KB Output is correct

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

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