Submission #528562

#	Time	Username	Problem	Language	Result	Execution time	Memory
528562		HappyPacMan	Comparing Plants (IOI20_plants)	C++14	100 / 100	1518 ms	94260 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 8;
const int mlog = 20;
const int inf = 1e7;
int N,K,seg[4*maxn],lazy[4*maxn],indexing=1,arr[maxn],rev[maxn],lf[mlog][maxn],sl[mlog][maxn],rg[mlog][maxn],sr[mlog][maxn];

void push(int id){
    lazy[id<<1] += lazy[id];
    lazy[id<<1|1] += lazy[id];
    seg[id<<1] += lazy[id];
    seg[id<<1|1] += lazy[id];
    lazy[id] = 0;
}
void upd(int id,int tl,int tr,int ul,int ur,int v){
    if(tl > tr || ul > tr || ur < tl) return;
    if(ul <= tl && tr <= ur){
        seg[id] += v;
        lazy[id] += v;
        return;
    }
    int tm = (tl+tr)/2;
    push(id);
    upd(id<<1,tl,tm,ul,ur,v);
    upd(id<<1|1,tm+1,tr,ul,ur,v);
    seg[id] = min(seg[id<<1],seg[id<<1|1]);
}
int qryfull(int id,int tl,int tr){
    if(seg[id] != 0) return -1;
    if(tl == tr) return tl;
    int tm = (tl+tr)/2;
    push(id);
    if(seg[id<<1] != 0) return qryfull(id<<1|1,tm+1,tr);
    else return qryfull(id<<1,tl,tm);
}

void init(int k, std::vector<int> r){
    K = k;
    N = r.size();
    for(int i=0;i<N;i++) upd(1,0,N-1,i,i,r[i]);
    set<int> lst,vld;
    int temp = N;
    auto Check = [&](int x){
        x %= N;
        if(lst.empty()) return true;
        int tx = *prev(lst.lower_bound(x+N));
        if(x+N-tx < K) return false;
        return true;
    };
    while(temp--){
        while(true){
            int id = qryfull(1,0,N-1);
            if(id == -1) break;
            upd(1,0,N-1,id,id,inf);
            if(Check(id)) vld.insert(id);
            lst.insert(id);
            lst.insert(N+id);
            if(!lst.empty() && !Check(*(lst.upper_bound(id)))) vld.erase((*(lst.upper_bound(id)))%N);
        }
        int target = *(vld.begin());
        rev[indexing] = target;
        arr[target] = indexing++;
        if(target > 0) upd(1,0,N-1,max(0,target-K+1),target-1,-1);
        if(0 > target-K+1) upd(1,0,N-1,N+target-K+1,N-1,-1);
        vld.erase(target);
        lst.erase(target);
        lst.erase(target+N);
        if(!lst.empty() && Check(*(lst.upper_bound(target)))) vld.insert((*(lst.upper_bound(target)))%N);
    }
    set<int> st;
    for(int i=1-K;i<0;i++) st.insert(arr[N+i]);
    for(int i=0;i<N;i++){
        auto it = st.lower_bound(arr[i]);
        if(it == st.begin()) lf[0][i] = i;
        else lf[0][i] = rev[*prev(it)];
        sl[0][i] = (N+i-lf[0][i])%N;
        st.insert(arr[i]);
        st.erase(arr[(N+i-K+1)%N]);
    }
    st.clear();
    for(int i=1;i<K;i++) st.insert(arr[i]);
    for(int i=0;i<N;i++){
        auto it = st.lower_bound(arr[i]);
        if(it == st.begin()) rg[0][i] = i;
        else rg[0][i] = rev[*prev(it)];
        sr[0][i] = (N+rg[0][i]-i)%N;
        st.insert(arr[(i+K)%N]);
        st.erase(arr[(i+1)%N]);
    }
    st.clear();
    for(int i=1;i<mlog;i++){
        for(int j=0;j<N;j++){
            lf[i][j] = lf[i-1][lf[i-1][j]];
            sl[i][j] = min(inf,sl[i-1][j]+sl[i-1][lf[i-1][j]]);
            rg[i][j] = rg[i-1][rg[i-1][j]];
            sr[i][j] = min(inf,sr[i-1][j]+sr[i-1][rg[i-1][j]]);
        }
    }
}

bool comp(int x,int y){
    int tx = x;
    int dx = (N+x-y)%N;
    for(int i=mlog-1;i>=0;i--){
        if(sl[i][tx] <= dx){
            dx -= sl[i][tx];
            tx = lf[i][tx];
        }
    }
    int ty = x;
    int dy = (N+y-x)%N;
    for(int i=mlog-1;i>=0;i--){
        if(sr[i][ty] <= dy){
            dy -= sr[i][ty];
            ty = rg[i][ty];
        }
    }
    if(dx <= sl[0][tx] && arr[y] <= arr[tx]) return true;
    if(dy <= sr[0][ty] && arr[y] <= arr[ty]) return true;
    return false;
}

int compare_plants(int x, int y){
    bool a = comp(x,y);
    if(a) return -1;
    bool b = comp(y,x);
    if(b) return 1;
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 11 / 11
• Subtask 6: 15 / 15
• Subtask 7: 25 / 25