oj.uz

Submission #307986

# Submission time Handle Problem Language Result Execution time Memory
307986 2020-09-29T17:16:58 Z VEGAnn Comparing Plants (IOI20_plants) C++17
32 / 100
 1814 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;
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];
    }

    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:164:12: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
  164 |     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 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 117 ms 3260 KB Output is correct
7 Correct 252 ms 12012 KB Output is correct
8 Correct 1078 ms 90736 KB Output is correct
9 Correct 1086 ms 90352 KB Output is correct
10 Correct 1119 ms 90608 KB Output is correct
11 Correct 1125 ms 91760 KB Output is correct
12 Correct 1157 ms 91376 KB Output is correct
13 Correct 1167 ms 100588 KB Output is correct
14 Correct 945 ms 80888 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 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 6 ms 896 KB Output is correct
7 Correct 110 ms 5368 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 5 ms 896 KB Output is correct
10 Correct 110 ms 5312 KB Output is correct
11 Correct 146 ms 5496 KB Output is correct
12 Correct 112 ms 5496 KB Output is correct
13 Correct 105 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 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 6 ms 896 KB Output is correct
7 Correct 110 ms 5368 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 5 ms 896 KB Output is correct
10 Correct 110 ms 5312 KB Output is correct
11 Correct 146 ms 5496 KB Output is correct
12 Correct 112 ms 5496 KB Output is correct
13 Correct 105 ms 5368 KB Output is correct
14 Correct 232 ms 11600 KB Output is correct
15 Correct 1721 ms 81476 KB Output is correct
16 Correct 227 ms 11512 KB Output is correct
17 Correct 1789 ms 81432 KB Output is correct
18 Correct 1479 ms 91152 KB Output is correct
19 Correct 1020 ms 81304 KB Output is correct
20 Correct 1523 ms 81484 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 149 ms 4088 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 1 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 6 ms 512 KB Output is correct
7 Correct 33 ms 1144 KB Output is correct
8 Correct 22 ms 1152 KB Output is correct
9 Incorrect 31 ms 1144 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 1 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 4 ms 768 KB Output is correct
6 Correct 1297 ms 81748 KB Output is correct
7 Correct 1520 ms 81404 KB Output is correct
8 Correct 1814 ms 81400 KB Output is correct
9 Incorrect 1743 ms 81420 KB Output isn't correct
10 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 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 117 ms 3260 KB Output is correct
7 Correct 252 ms 12012 KB Output is correct
8 Correct 1078 ms 90736 KB Output is correct
9 Correct 1086 ms 90352 KB Output is correct
10 Correct 1119 ms 90608 KB Output is correct
11 Correct 1125 ms 91760 KB Output is correct
12 Correct 1157 ms 91376 KB Output is correct
13 Correct 1167 ms 100588 KB Output is correct
14 Correct 945 ms 80888 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 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 6 ms 896 KB Output is correct
21 Correct 110 ms 5368 KB Output is correct
22 Correct 3 ms 512 KB Output is correct
23 Correct 5 ms 896 KB Output is correct
24 Correct 110 ms 5312 KB Output is correct
25 Correct 146 ms 5496 KB Output is correct
26 Correct 112 ms 5496 KB Output is correct
27 Correct 105 ms 5368 KB Output is correct
28 Correct 232 ms 11600 KB Output is correct
29 Correct 1721 ms 81476 KB Output is correct
30 Correct 227 ms 11512 KB Output is correct
31 Correct 1789 ms 81432 KB Output is correct
32 Correct 1479 ms 91152 KB Output is correct
33 Correct 1020 ms 81304 KB Output is correct
34 Correct 1523 ms 81484 KB Output is correct
35 Correct 1 ms 384 KB Output is correct
36 Correct 1 ms 384 KB Output is correct
37 Incorrect 149 ms 4088 KB Output isn't correct
38 Halted 0 ms 0 KB -