oj.uz

Submission #302078

# Submission time Handle Problem Language Result Execution time Memory
302078 2020-09-18T12:25:59 Z VEGAnn Comparing Plants (IOI20_plants) C++14
5 / 100
 118 ms 9960 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 68 ms 3196 KB Output is correct
7 Correct 84 ms 3704 KB Output is correct
8 Correct 111 ms 8184 KB Output is correct
9 Correct 118 ms 8184 KB Output is correct
10 Correct 112 ms 8184 KB Output is correct
11 Correct 112 ms 8300 KB Output is correct
12 Correct 111 ms 9064 KB Output is correct
13 Correct 108 ms 9704 KB Output is correct
14 Correct 113 ms 9960 KB Output is correct

Subtask #2
0 / 14.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 68 ms 3196 KB Output is correct
7 Correct 84 ms 3704 KB Output is correct
8 Correct 111 ms 8184 KB Output is correct
9 Correct 118 ms 8184 KB Output is correct
10 Correct 112 ms 8184 KB Output is correct
11 Correct 112 ms 8300 KB Output is correct
12 Correct 111 ms 9064 KB Output is correct
13 Correct 108 ms 9704 KB Output is correct
14 Correct 113 ms 9960 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 512 KB Output is correct
17 Incorrect 1 ms 384 KB Output isn't correct
18 Halted 0 ms 0 KB -