Submission #528135

#	Time	Username	Problem	Language	Result	Execution time	Memory
528135		HappyPacMan	Comparing Plants (IOI20_plants)	C++14	5 / 100	1363 ms	72508 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
using namespace std;    
const int maxn = 2e5 + 8;
const int mlog = 20;
const int inf = 1e9;
int N,K,seg[4*maxn],lazy[4*maxn],indexing=0,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);
}
int qrypart(int id,int tl,int tr,int ql){
    if(tl == tr) return seg[id];
    int tm = (tl+tr)/2;
    push(id);
    if(tm < ql) return qrypart(id<<1|1,tm+1,tr,ql);
    else return qrypart(id<<1,tl,tm,ql);
}

void rec(int x){
    for(int i=1-K;i<0;i++) if(qrypart(1,0,N-1,(x+N+i)%N) == 0){
        rec((x+N+i)%N);
        return;
    }
    if(qrypart(1,0,N-1,x) != 0) return;
    upd(1,0,N-1,x,x,inf);
    if(x > 0) upd(1,0,N-1,max(0,x-K+1),x-1,-1);
    if(0 > x-K+1) upd(1,0,N-1,N+x-K+1,N-1,-1);
    rev[indexing] = x;
    arr[x] = indexing++;
}

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]);
    while(qryfull(1,0,N-1) != -1) rec(qryfull(1,0,N-1));
    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] = sl[i-1][j]+sl[i-1][lf[i-1][j]];
            rg[i][j] = rg[i-1][rg[i-1][j]];
            sr[i][j] = 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 <= sl[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: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25