oj.uz

Submission #1008720

# Submission time Handle Problem Language Result Execution time Memory
1008720 2024-06-26T16:59:07 Z bachhoangxuan Comparing Plants (IOI20_plants) C++17
14 / 100
 550 ms 110916 KB 
#include "plants.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;
const int maxl = 25;
const int inf = 1e9;
int n,k;
vector<int> R,H;
set<int> ss,cc;
int lt[maxn][maxl],rt[maxn][maxl];

void cal(int x,int y){
    cc.erase(y);
    if((y-x+n)%n>=k){
        cc.insert(y);
    }
}
void add(int x){
    if(ss.empty()){
        ss.insert(x);
        cc.insert(x);
        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){
    lazy[id]=0;
    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;
        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]);
}
vector<int> solve(vector<int> r){
    R=r;
    vector<int> p(n);
    ss.clear();cc.clear();
    build(0,n-1,1);
    for(int i=n-1;i>=0;i--){
        get(0,n-1,1);
        int x=*cc.begin();
        if((int)cc.size()>1 && x==0) x=*cc.rbegin();
        p[x]=i;del(x);
        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);
        }
    }
    return p;
}

void init(int _k, std::vector<int> r) {
    k=_k;
    n=(int)r.size();
    H=solve(r);

    set<pair<int,int>> S;
    for(int i=0;i<k;i++) S.insert({H[i],i});
    for(int i=0;i<n;i++){
        auto it=S.erase(S.lower_bound({H[i],i}));
        if(it!=S.begin()) it=prev(it),rt[i][0]=(it->second-i+n)%n;
        S.insert({H[(i+k)%n],(i+k)%n});
    }
    S.clear();
    for(int i=1;i<=k;i++) S.insert({H[(n-i)%n],(n-i)%n});
    for(int i=0;i<n;i++){
        S.erase({H[(i-k+n)%n],(i-k+n)%n});
        auto it=S.insert({H[i],i}).first;
        if(it!=S.begin()) it=prev(it),lt[i][0]=(i-it->second+n)%n;
    }
    for(int i=0;i<n;i++) assert(lt[i][0]>=0 && rt[i][0]>=0);
    for(int j=1;j<18;j++){
        for(int i=0;i<n;i++){
            int nr=(i+rt[i][j-1])%n;
            rt[i][j]=rt[i][j-1]+rt[nr][j-1];
            int nl=(i-(lt[i][j-1]%n)+n)%n;
            lt[i][j]=lt[i][j-1]+lt[nl][j-1];
        }
    }
}

bool get_lt(int x,int y){
    int d=(x-y+n)%n;
    for(int i=17;i>=0;i--){
        if(lt[x][i]<=d) d-=lt[x][i],x=(x-lt[x][i]%n+n)%n;
    }
    return (x-y+n)%n<k && H[x]>=H[y];
}

bool get_rt(int x,int y){
    int d=(y-x+n)%n;
    for(int i=17;i>=0;i--){
        if(rt[x][i]<=d) d-=rt[x][i],x=(x+rt[x][i])%n;
    }
    return (y-x+n)%n<k && H[x]>=H[y];
}

int compare_plants(int x, int y) {
    /*
    if(get_lt(x,y) || get_rt(x,y)) return 1;
    if(get_lt(y,x) || get_rt(y,x)) return -1;
	return 0;
	*/
    return (H[x]>H[y]?1:-1);
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 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 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 43 ms 4444 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 38 ms 4528 KB Output is correct
11 Correct 35 ms 4432 KB Output is correct
12 Correct 33 ms 4688 KB Output is correct
13 Correct 53 ms 4688 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 43 ms 4444 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 38 ms 4528 KB Output is correct
11 Correct 35 ms 4432 KB Output is correct
12 Correct 33 ms 4688 KB Output is correct
13 Correct 53 ms 4688 KB Output is correct
14 Correct 66 ms 8496 KB Output is correct
15 Runtime error 550 ms 110916 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 33 ms 3580 KB Output is correct
4 Correct 225 ms 52288 KB Output is correct
5 Correct 274 ms 49728 KB Output is correct
6 Correct 290 ms 49216 KB Output is correct
7 Correct 379 ms 49472 KB Output is correct
8 Runtime error 510 ms 107844 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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