Submission #357774

#	Time	Username	Problem	Language	Result	Execution time	Memory
357774		doowey	Comparing Plants (IOI20_plants)	C++14	100 / 100	2787 ms	94136 KiB

plants

#include <bits/stdc++.h>
#include "plants.h"

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

#define fi first
#define se second
#define mp make_pair

const int N = (int)2e5 + 100;
int A[N];
int vl[N];

struct Node{
    pii valid; // = r + vl
    pii zero; // = r
    int rlazy;
    int vllazy;
};

Node T[N * 4 + 512];

void push(int node, int cl, int cr){
    T[node].valid.fi += T[node].rlazy + T[node].vllazy;
    T[node].zero.fi += T[node].rlazy;
    if(cl != cr){
        T[node*2].rlazy += T[node].rlazy;
        T[node*2+1].rlazy += T[node].rlazy;
        T[node*2].vllazy += T[node].vllazy;
        T[node*2+1].vllazy += T[node].vllazy;
    }
    T[node].rlazy = 0;
    T[node].vllazy = 0;
}

void upd(int node, int cl, int cr, int tl, int tr, int typ, int v){
    push(node, cl, cr);
    if(cr < tl || cl > tr)
        return;
    if(cl >= tl && cr <= tr){
        if(typ == 0) T[node].rlazy = v;
        else T[node].vllazy = v;
        push(node, cl, cr);
        return;
    }
    int mid = (cl + cr) / 2;
    upd(node * 2, cl, mid, tl, tr, typ, v);
    upd(node * 2 + 1, mid + 1, cr, tl, tr, typ, v);
    T[node].valid = min(T[node*2].valid, T[node*2+1].valid);
    T[node].zero = min(T[node*2].zero, T[node*2+1].zero);
}

pii get(int node, int cl, int cr, int tl, int tr, int ta){
    push(node, cl, cr);
    if(cr < tl || cl > tr)
        return mp((int)1e9, (int)1e9);
    if(cl >= tl && cr <= tr){
        if(ta == 0)
            return T[node].zero;
        else
            return T[node].valid;
    }
    int mid = (cl + cr) / 2;
    return min(get(node * 2, cl, mid, tl, tr, ta), get(node * 2 + 1, mid + 1, cr, tl, tr, ta));
}

vector<int> r;

void build(int node, int cl, int cr){
    if(cl == cr){
        T[node].valid = mp(r[cl], cl);
        T[node].zero = mp(r[cl], cl);
        return;
    }
    int mid = (cl + cr) / 2;
    build(node * 2, cl, mid);
    build(node * 2 + 1, mid + 1, cr);
    T[node].valid = min(T[node * 2].valid, T[node * 2 + 1].valid);
    T[node].zero = min(T[node * 2].zero, T[node * 2 + 1].zero);
}

int n, k;

void upd_zero(int ii, int sign){
    int nx = (ii + k - 1) % n;
    if(nx > ii){
        upd(1, 0, n - 1, ii + 1, nx, 1, sign);
    }
    else{
        upd(1, 0, n - 1, ii + 1, n - 1, 1, sign);
        upd(1, 0, n - 1, 0, nx, 1, sign);
    }
}

vector<int> getz(int li, int ri){
    vector<int> soln;
    pii cc;
    while(li <= ri){
        cc = get(1, 0, n - 1, li, ri, 0);
        if(cc.fi != 0) return soln;
        soln.push_back(cc.se);
        li = cc.se + 1;
    }
    return soln;
}

const int LOG = 18;
int lef[LOG][N];
int rig[LOG][N];
int cl[LOG][N];
int cr[LOG][N];

void init(int k_, vector<int> r_) {
    r = r_;
    k = k_;
    n = r.size();
    build(1, 0, n - 1);
    for(int i = 0 ; i < n; i ++ ){
        if(r[i] == 0){
            upd_zero(i,+1);
        }
    }

    int st;
    int pv;
    int nx;
    for(int id = n - 1; id >= 0 ; id -- ){
        st = T[1].valid.se;
        A[st] = id;
        pv = (st - (k - 1) + n) % n;
        upd(1, 0, n - 1, st, st, 0, (int)1e9);
        upd_zero(st,-1);
        vector<int> nwz, cc;
        if(pv < st){
            upd(1, 0, n - 1, pv, st - 1, 0, -1);
            cc = getz(pv, st - 1);
            for(auto q : cc) nwz.push_back(q);
        }
        else{
            upd(1, 0, n - 1, 0, st - 1, 0, -1);
            upd(1, 0, n - 1, pv, n - 1, 0, -1);
            cc = getz(0, st - 1);
            for(auto q : cc) nwz.push_back(q);
            cc = getz(pv, n - 1);
            for(auto q : cc) nwz.push_back(q);
        }
        for(auto x : nwz){
            upd_zero(x,+1);
        }
    }
    multiset<pii> alx;
    for(int i = n - 1; i >= n - (k - 1); i -- ){
        alx.insert(mp(A[i], i));
    }
    for(int i = 0 ; i < n; i ++ ){
        auto it = alx.lower_bound(mp(A[i],-1));
        if(it == alx.begin()){
            lef[0][i] = -1;
        }
        else{
            it -- ;
            cl[0][i] = (it->se > i);
            lef[0][i] = it->se;
        }
        pv = (i - (k - 1) + n) % n;
        alx.erase(mp(A[pv], pv));
        alx.insert(mp(A[i],i));
    }
    alx.clear();
    for(int i = 1; i < k ; i ++ ){
        alx.insert(mp(A[i],i));
    }
    for(int i = 0; i < n; i ++ ){
        auto it = alx.lower_bound(mp(A[i],-1));
        if(it == alx.begin()){
            rig[0][i] = -1;
        }
        else{
            it -- ;
            cr[0][i] = (it->se < i);
            rig[0][i] = it->se;
        }
        if(i < n){
            alx.erase(mp(A[i + 1], i + 1));
            alx.insert(mp(A[(i + k) % n], (i + k) % n));
        }
    }
    for(int lg = 1; lg < LOG; lg ++ ){
        for(int i = 0 ; i < n; i ++ ){
            lef[lg][i]=rig[lg][i]=-1;
            if(lef[lg-1][i] != -1){
                lef[lg][i]=lef[lg-1][lef[lg-1][i]];
                cl[lg][i] = (cl[lg-1][i] | cl[lg-1][lef[lg-1][i]]);
            }
            if(rig[lg-1][i] != -1){
                rig[lg][i]=rig[lg-1][rig[lg-1][i]];
                cr[lg][i] = (cr[lg-1][i] | cr[lg-1][rig[lg-1][i]]);
            }
        }
    }
}

int compare_plants(int x, int y) {
    int go = x;
    for(int i = LOG - 1; i >= 0 ; i -- ){
        if(lef[i][go] != -1 && cl[i][go] != 1)
            go = lef[i][go];
    }
    if(lef[0][go] != -1){
        if(lef[0][go] > y){
            go = lef[0][go];
            for(int i = LOG - 1; i >= 0 ; i -- ){
                if(lef[i][go] != -1 && cl[i][go] != 1 && lef[i][go] > y)
                    go = lef[i][go];
            }
            if((go - y + n) % n < k){
                if(A[go] > A[y]) return +1;
            }
        }
        else{
            if(A[go] > A[y]) return +1;
        }
    }
    go = x;
    for(int i = LOG - 1; i >= 0 ; i -- ){
        if(rig[i][go] != -1 && cr[i][go] != 1 && rig[i][go] < y){
            go = rig[i][go];
        }
    }
    if(y - go < k){
        if(A[go] > A[y]) return +1;
    }
    //
    go = y;
    for(int i = LOG - 1; i >= 0 ; i -- ){
        if(lef[i][go] != -1 && cl[i][go] != 1 && lef[i][go] > x){
            go = lef[i][go];
        }
    }
    if(go - x < k){
        if(A[go] > A[x]) return -1;
    }
    //
    go = y;
    for(int i = LOG - 1; i >= 0 ; i -- ){
        if(rig[i][go] != -1 && cr[i][go] != 1)
            go = rig[i][go];
    }
    if(rig[0][go] != -1){
        if(rig[0][go] < x){
            for(int i = LOG - 1; i >= 0 ; i -- ){
                if(rig[i][go] != -1 && cr[i][go] != 1 && cr[i][go] < x){
                    go = rig[i][go];
                }
            }
            if(x - go < k){
                if(A[go] > A[x]) return -1;
            }
        }
        else{
            if(A[go] > A[x]) return -1;
        }
    }
    return 0;
}

Compilation message (stderr)

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:129:9: warning: unused variable 'nx' [-Wunused-variable]
  129 |     int nx;
      |         ^~

• 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