Submission #302078

#	Time	Username	Problem	Language	Result	Execution time	Memory
302078		VEGAnn	Comparing Plants (IOI20_plants)	C++14	5 / 100	118 ms	9960 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
#define PB push_back
#define sz(x) ((int)x.size())
#define i2 array<int,2>
using namespace std;
const int N = 200100;
const int oo = 2e9;
set<int> locs;
set<int>::iterator iter;
set<i2> mx;
vector<int> vc, glob;
int per[N], psh[4 * N], n, pre[N][2], suf[N][2], glob_k;
i2 st[4 * N];

int nxt(int x){ return (x + 1) % n;}

int get(int tp, int x) {
    return (pre[x][tp] == x ? x : pre[x][tp] = get(tp, pre[x][tp]));
}

void link(int tp, int fi, int se){
    fi = get(tp, fi);
    se = get(tp, se);

    pre[fi][tp] = se;
}

void build(int v, int l, int r){
    if (l == r){
        st[v] = {glob[l], l};
        return;
    }

    int md = (l + r) >> 1;

    build(v + v, l, md);
    build(v + v + 1, md + 1, r);

    st[v] = min(st[v + v], st[v + v + 1]);
}

void push(int v){
    if (psh[v] != 0){
//        cerr << st[v][0] << " " << st[v][1] << '\n';
        st[v][0] += psh[v];

//        cerr << st[v][0] << " " << st[v][1] << '\n';

        if (v + v + 1 < 4 * N){
            psh[v + v] += psh[v];
            psh[1 + v + v] += psh[v];
        }

        psh[v] = 0;
    }
}

void del(int v, int tl, int tr, int l, int r, int vl){
    push(v);

    if (l > r) return;

    if (tl == l && tr == r) {
        psh[v] = vl;
        push(v);
        return;
    }

    int md = (tl + tr) >> 1;

    del(v + v, tl, md, l, min(r, md), vl);
    del(v + v + 1, md + 1, tr, max(md + 1, l), r, vl);

    st[v] = min(st[v + v], st[v + v + 1]);
}

i2 get(int v, int tl, int tr, int l, int r){
    push(v);

    if (l > r) return {oo, 0};

    if (tl == l && tr == r) return st[v];

    int md = (tl + tr) >> 1;

    return min(get(v + v, tl, md, l, min(r, md)),
               get(v + v + 1, md + 1, tr, max(md + 1, l), r));
}

int dist(int fi, int se){
    if (se > fi)
        return se - fi;
    else return se - fi + n;
}

void uhodi(int vl){
    if (sz(locs) <= 2){
        locs.erase(vl);
        mx.clear();
    } else {
        iter = locs.find(vl);

        int PREV, NEXT;

        if (iter == locs.begin())
            PREV = (*(--locs.end()));
        else PREV = (*prev(iter));

        if (next(iter) == locs.end())
            NEXT = (*locs.begin());
        else NEXT = (*next(iter));

        mx.erase({dist(PREV, vl), vl});
        mx.erase({dist(vl, NEXT), NEXT});

        locs.erase(iter);

        mx.insert({dist(PREV, NEXT), NEXT});
    }
}

void prihodi(int vl){
    if (sz(locs) == 0){
        locs.insert(vl);
        return;
    }

    locs.insert(vl);

    iter = locs.find(vl);

    int PREV, NEXT;

    if (iter == locs.begin())
        PREV = (*(--locs.end()));
    else PREV = (*prev(iter));

    if (next(iter) == locs.end())
        NEXT = (*locs.begin());
    else NEXT = (*next(iter));

    mx.erase({dist(PREV, NEXT), NEXT});

    mx.insert({dist(PREV, vl), vl});
    mx.insert({dist(vl, NEXT), NEXT});
}

void init(int k, vector<int> r) {
    n = sz(r);

    glob_k = 2;

    if (k == 2){
        for (int i = 0; i < n; i++){
            pre[i][0] = pre[i][1] = i;
        }

        glob = r;

        for (int i = 0; i < n; i++)
            if (r[i] == 0)
                link(0, i, nxt(i));
            else link(1, i, nxt(i));

        suf[n][0] = suf[n][1] = 0;

        for (int i = n - 1; i >= 0; i--){
            suf[i][0] = suf[i + 1][0];
            suf[i][1] = suf[i + 1][1];

            suf[i][r[i] ^ 1]++;
        }
        return;
    }

    glob = r;

    build(1, 0, n - 1);

    vc.clear();

    for (int i = 0; i < n; i++)
        if (r[i] == 0)
            vc.PB(i);

    for (int it = 0; it < sz(vc); it++){
        int cur = vc[it];
        int nxt = vc[(it + 1) % sz(vc)];

        locs.insert(cur);

        del(1, 0, n - 1, cur, cur, oo);

        if (sz(vc) == 1) continue;

        if (cur == vc.back()){
            mx.insert({nxt + n - cur, nxt});
        } else {
            mx.insert({nxt - cur, nxt});
        }
    }

    for (int it = n - 1; it >= 0; it--){
        assert(sz(locs) > 0);

        int cand = -1;

        if (sz(locs) == 1){
            int vl = (*locs.begin());

            cand = vl;

            uhodi(vl);
        } else {
            cand = (*(--mx.end()))[1];

            uhodi(cand);
        }

        // delete with segment tree

//        cerr << st[2][0] << " " << st[2][1] << '\n';

        int rt = cand, lf = cand - k + 1;

        per[cand] = it;

        if (lf < 0){
            lf += n;

            del(1, 0, n - 1, 0, rt, -1);

            i2 cur = get(1, 0, n - 1, 0, rt);

//            cerr << cur[0] << " " <<cur[1] << '\n';

            while (cur[0] == 0){
                prihodi(cur[1]);
                del(1, 0, n - 1, cur[1], cur[1], oo);
                cur = get(1, 0, n - 1, 0, rt);
            }

            del(1, 0, n - 1, lf, n - 1,  -1);

            cur = get(1, 0, n - 1, lf, n - 1);

            while (cur[0] == 0){
                prihodi(cur[1]);
                del(1, 0, n - 1, cur[1], cur[1], oo);
                cur = get(1, 0, n - 1, lf, n - 1);
            }
        } else {
            del(1, 0, n - 1, lf, rt, -1);

            i2 cur = get(1, 0, n - 1, lf, rt);

            while (cur[0] == 0){
                prihodi(cur[1]);
                del(1, 0, n - 1, cur[1], cur[1], oo);
                cur = get(1, 0, n - 1, lf, rt);
            }

//            cerr << cur[0] << " " <<cur[1] << '\n';
        }
    }

    return;
}

int compare_plants(int x, int y) {
    if (glob_k == 2){
        if (get(0, x) == get(0, y)){
            if (x > y){
                if (suf[y][0] - suf[x][0] > 0)
                    return 1;
                else return -1;
            } else {
                if (suf[x][0] - suf[y][0] > 0)
                    return -1;
                else return 1;
            }
        }

        if (get(1, x) == get(1, y)){
            if (x > y){
                if (suf[y][1] - suf[x][1] > 0)
                    return -1;
                else return 1;
            } else {
                if (suf[x][1] - suf[y][1] > 0)
                    return 1;
                else return -1;
            }
        }

        return 0;
    } else {
        return (per[x] > per[y] ? 1 : -1);
    }
}

• 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