oj.uz

Submission #307997

# Submission time Handle Problem Language Result Execution time Memory
307997 2020-09-29T17:41:48 Z VEGAnn Comparing Plants (IOI20_plants) C++17
32 / 100
 1728 ms 131948 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;
typedef long long ll;
const int N = 200100;
const int oo = 2e9;
const int PW = 20;
set<int> locs;
set<int>::iterator iter;
set<i2> mx;
vector<int> vc, glob;
int per[N], psh[4 * N], n, nt[2][N], up[2][N][PW], k;
ll len[2][N][PW];
i2 st[4 * N], mn[4 * N];

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){
        st[v][0] += psh[v];

        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 BUILD(int v, int l, int r){
    mn[v] = {oo, l};

    if (l == r) return;

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

    BUILD(v + v, l, md);
    BUILD(v + v + 1, md + 1, r);
}

void update_mn(int v, int l, int r, int ps, int vl){
    if (l == r){
        mn[v] = {vl, l};
        return;
    }

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

    if (ps <= md)
        update_mn(v + v, l, md, ps, vl);
    else update_mn(v + v + 1, md + 1, r, ps, vl);

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

i2 get_mn(int v, int tl, int tr, int l, int r){
    if (l > r) return {oo, 0};

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

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

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

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

    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});
        }
    }

    BUILD(1, 0, n - 1);

    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

        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);

            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);
            }

            cur = min(get_mn(1, 0, n - 1, 0, rt), get_mn(1, 0, n - 1, lf, n - 1));

            if (cur[0] == oo)
                nt[0][cand] = cand;
            else nt[0][cand] = cur[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);
            }

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

            if (cur[0] == oo)
                nt[0][cand] = cand;
            else nt[0][cand] = cur[1];
        }

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

        if (rt >= n){
            rt -= n;

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

            if (cur[0] == oo)
                nt[1][cand] = cand;
            else nt[1][cand] = cur[1];
        } else {
            i2 cur = get_mn(1, 0, n - 1, lf, rt);

            if (cur[0] == oo)
                nt[1][cand] = cand;
            else nt[1][cand] = cur[1];
        }

        update_mn(1, 0, n - 1, cand, per[cand]);
    }

    for (int i = 0; i < n; i++){
        up[0][i][0] = nt[0][i];
        up[1][i][0] = nt[1][i];

        len[0][i][0] = i - nt[0][i];
        if (len[0][i][0] < 0) len[0][i][0] += n;

        len[1][i][0] = nt[1][i] - i;
        if (len[1][i][0] < 0) len[1][i][0] += n;
    }

    for (int po = 1; po < PW; po++)
    for (int i = 0; i < n; i++){
        up[0][i][po] = up[0][up[0][i][po - 1]][po - 1];
        up[1][i][po] = up[1][up[1][i][po - 1]][po - 1];

        len[0][i][po] = len[0][i][po - 1] + len[0][up[0][i][po - 1]][po - 1];
        len[1][i][po] = len[1][i][po - 1] + len[1][up[1][i][po - 1]][po - 1];
    }

    return;
}

bool smaller(int x, int y){
    // left direction

    int loc = x, sum = 0;

    for (int po = PW - 1; po >= 0; po--){
        int nw = up[0][loc][po];

        if (sum + len[0][loc][po] >= n) continue;

        int dst = nw - y;

        if (dst < 0) dst += n;

        if (dst < k) continue;

        if (x > y){
            if (nw > y && nw <= x) {
                loc = nw;
                sum += len[0][loc][po];
            }
        } else {
            if (nw <= x || nw > y) {
                loc = nw;
                sum += len[0][loc][po];
            }
        }
    }

    int dst = loc - y;

    if (dst < 0) dst += n;

    if (dst >= k)
        loc = up[0][loc][0];

    dst = loc - y;

    if (dst < 0) dst += n;

    if (dst < k && per[loc] < per[y])
        return 1;

    //right direction

    loc = x; sum = 0;

    for (int po = PW - 1; po >= 0; po--){
        int nw = up[1][loc][po];

        if (sum + len[1][loc][po] >= n) continue;

        int dst = y - nw;

        if (dst < 0) dst += n;

        if (dst < k) continue;

        if (x < y){
            if (nw < y && nw >= x) {
                loc = nw;
                sum += len[1][loc][po];
            }
        } else {
            if (nw >= x || nw < y) {
                loc = nw;
                sum += len[1][loc][po];
            }
        }
    }

    dst = y - loc;

    if (dst < 0) dst += n;

    if (dst >= k)
        loc = up[1][loc][0];

    dst = y - loc;

    if (dst < 0) dst += n;

    if (dst < k && per[loc] < per[y])
        return 1;

    return 0;
}

int compare_plants(int x, int y) {
    if (smaller(x, y)) return -1;
    if (smaller(y, x)) return +1;

    return 0;
}

Compilation message

plants.cpp: In function 'std::array<int, 2> get_mn(int, int, int, int, int)':
plants.cpp:165:12: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
  165 |     if (tl == l & tr == r) return mn[v];
      |         ~~~^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 121 ms 3192 KB Output is correct
7 Correct 286 ms 14972 KB Output is correct
8 Correct 1118 ms 122224 KB Output is correct
9 Correct 1156 ms 121544 KB Output is correct
10 Correct 1181 ms 121968 KB Output is correct
11 Correct 1197 ms 123056 KB Output is correct
12 Correct 1220 ms 122532 KB Output is correct
13 Correct 1241 ms 131948 KB Output is correct
14 Correct 1008 ms 112248 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 6 ms 1024 KB Output is correct
7 Correct 120 ms 6264 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 6 ms 1024 KB Output is correct
10 Correct 114 ms 6060 KB Output is correct
11 Correct 152 ms 6264 KB Output is correct
12 Correct 111 ms 6140 KB Output is correct
13 Correct 110 ms 6136 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 6 ms 1024 KB Output is correct
7 Correct 120 ms 6264 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 6 ms 1024 KB Output is correct
10 Correct 114 ms 6060 KB Output is correct
11 Correct 152 ms 6264 KB Output is correct
12 Correct 111 ms 6140 KB Output is correct
13 Correct 110 ms 6136 KB Output is correct
14 Correct 247 ms 14712 KB Output is correct
15 Correct 1688 ms 112672 KB Output is correct
16 Correct 237 ms 14712 KB Output is correct
17 Correct 1698 ms 112760 KB Output is correct
18 Correct 1508 ms 122608 KB Output is correct
19 Correct 1053 ms 112888 KB Output is correct
20 Correct 1542 ms 112760 KB Output is correct

Subtask #4
0 / 17.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 Incorrect 154 ms 4344 KB Output isn't correct
4 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 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 4 ms 512 KB Output is correct
7 Correct 36 ms 1144 KB Output is correct
8 Correct 22 ms 1152 KB Output is correct
9 Incorrect 31 ms 1280 KB Output isn't correct
10 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 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 4 ms 896 KB Output is correct
6 Correct 1297 ms 112888 KB Output is correct
7 Correct 1479 ms 112892 KB Output is correct
8 Correct 1728 ms 112680 KB Output is correct
9 Correct 1654 ms 112760 KB Output is correct
10 Correct 1274 ms 117492 KB Output is correct
11 Correct 1563 ms 113604 KB Output is correct
12 Correct 1193 ms 119152 KB Output is correct
13 Incorrect 1366 ms 114296 KB Output isn't correct
14 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 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 121 ms 3192 KB Output is correct
7 Correct 286 ms 14972 KB Output is correct
8 Correct 1118 ms 122224 KB Output is correct
9 Correct 1156 ms 121544 KB Output is correct
10 Correct 1181 ms 121968 KB Output is correct
11 Correct 1197 ms 123056 KB Output is correct
12 Correct 1220 ms 122532 KB Output is correct
13 Correct 1241 ms 131948 KB Output is correct
14 Correct 1008 ms 112248 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 0 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 6 ms 1024 KB Output is correct
21 Correct 120 ms 6264 KB Output is correct
22 Correct 3 ms 512 KB Output is correct
23 Correct 6 ms 1024 KB Output is correct
24 Correct 114 ms 6060 KB Output is correct
25 Correct 152 ms 6264 KB Output is correct
26 Correct 111 ms 6140 KB Output is correct
27 Correct 110 ms 6136 KB Output is correct
28 Correct 247 ms 14712 KB Output is correct
29 Correct 1688 ms 112672 KB Output is correct
30 Correct 237 ms 14712 KB Output is correct
31 Correct 1698 ms 112760 KB Output is correct
32 Correct 1508 ms 122608 KB Output is correct
33 Correct 1053 ms 112888 KB Output is correct
34 Correct 1542 ms 112760 KB Output is correct
35 Correct 1 ms 384 KB Output is correct
36 Correct 1 ms 384 KB Output is correct
37 Incorrect 154 ms 4344 KB Output isn't correct
38 Halted 0 ms 0 KB -