oj.uz

Submission #308013

# Submission time Handle Problem Language Result Execution time Memory
308013 2020-09-29T18:24:02 Z VEGAnn Comparing Plants (IOI20_plants) C++17
32 / 100
 1676 ms 100588 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;
int 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];

        len[0][i][po] = min(len[0][i][po], n + n);
        len[1][i][po] = min(len[1][i][po], n + n);
    }

    return;
}

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

    int loc = x, sum = 0;

    int dlen = x - y;

    if (dlen < 0) dlen += n;

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

        if (sum + len[0][loc][po] >= dlen) 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;

    dlen = y - x;

    if (dlen < 0) dlen += n;

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

        if (sum + len[1][loc][po] >= dlen) 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 1 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 115 ms 3192 KB Output is correct
7 Correct 258 ms 11896 KB Output is correct
8 Correct 1059 ms 90736 KB Output is correct
9 Correct 1092 ms 90352 KB Output is correct
10 Correct 1115 ms 90684 KB Output is correct
11 Correct 1123 ms 91504 KB Output is correct
12 Correct 1165 ms 91120 KB Output is correct
13 Correct 1168 ms 100588 KB Output is correct
14 Correct 939 ms 80928 KB Output is correct

Subtask #2
14.0 / 14.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 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 5 ms 896 KB Output is correct
7 Correct 114 ms 5384 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 5 ms 896 KB Output is correct
10 Correct 105 ms 5372 KB Output is correct
11 Correct 142 ms 5496 KB Output is correct
12 Correct 107 ms 5400 KB Output is correct
13 Correct 103 ms 5368 KB Output is correct

Subtask #3
13.0 / 13.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 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 5 ms 896 KB Output is correct
7 Correct 114 ms 5384 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 5 ms 896 KB Output is correct
10 Correct 105 ms 5372 KB Output is correct
11 Correct 142 ms 5496 KB Output is correct
12 Correct 107 ms 5400 KB Output is correct
13 Correct 103 ms 5368 KB Output is correct
14 Correct 203 ms 11512 KB Output is correct
15 Correct 1676 ms 81340 KB Output is correct
16 Correct 208 ms 11640 KB Output is correct
17 Correct 1671 ms 81468 KB Output is correct
18 Correct 1438 ms 91216 KB Output is correct
19 Correct 991 ms 81400 KB Output is correct
20 Correct 1472 ms 81400 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 0 ms 384 KB Output is correct
3 Incorrect 139 ms 4004 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 Incorrect 32 ms 1144 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 15.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 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 4 ms 768 KB Output is correct
6 Incorrect 1271 ms 81656 KB Output isn't correct
7 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 1 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 115 ms 3192 KB Output is correct
7 Correct 258 ms 11896 KB Output is correct
8 Correct 1059 ms 90736 KB Output is correct
9 Correct 1092 ms 90352 KB Output is correct
10 Correct 1115 ms 90684 KB Output is correct
11 Correct 1123 ms 91504 KB Output is correct
12 Correct 1165 ms 91120 KB Output is correct
13 Correct 1168 ms 100588 KB Output is correct
14 Correct 939 ms 80928 KB Output is correct
15 Correct 1 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 5 ms 896 KB Output is correct
21 Correct 114 ms 5384 KB Output is correct
22 Correct 3 ms 512 KB Output is correct
23 Correct 5 ms 896 KB Output is correct
24 Correct 105 ms 5372 KB Output is correct
25 Correct 142 ms 5496 KB Output is correct
26 Correct 107 ms 5400 KB Output is correct
27 Correct 103 ms 5368 KB Output is correct
28 Correct 203 ms 11512 KB Output is correct
29 Correct 1676 ms 81340 KB Output is correct
30 Correct 208 ms 11640 KB Output is correct
31 Correct 1671 ms 81468 KB Output is correct
32 Correct 1438 ms 91216 KB Output is correct
33 Correct 991 ms 81400 KB Output is correct
34 Correct 1472 ms 81400 KB Output is correct
35 Correct 1 ms 384 KB Output is correct
36 Correct 0 ms 384 KB Output is correct
37 Incorrect 139 ms 4004 KB Output isn't correct
38 Halted 0 ms 0 KB -