oj.uz

Submission #308003

# Submission time Handle Problem Language Result Execution time Memory
308003 2020-09-29T17:56:17 Z VEGAnn Comparing Plants (IOI20_plants) C++17
27 / 100
 4000 ms 91092 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;

    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;

    while (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
0 / 5.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 Execution timed out 4059 ms 384 KB Time limit exceeded
5 Halted 0 ms 0 KB -

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 5 ms 896 KB Output is correct
7 Correct 110 ms 5392 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 5368 KB Output is correct
11 Correct 148 ms 5500 KB Output is correct
12 Correct 108 ms 5624 KB Output is correct
13 Correct 107 ms 5368 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 5 ms 896 KB Output is correct
7 Correct 110 ms 5392 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 5368 KB Output is correct
11 Correct 148 ms 5500 KB Output is correct
12 Correct 108 ms 5624 KB Output is correct
13 Correct 107 ms 5368 KB Output is correct
14 Correct 224 ms 11576 KB Output is correct
15 Correct 1676 ms 81384 KB Output is correct
16 Correct 218 ms 11640 KB Output is correct
17 Correct 1670 ms 81388 KB Output is correct
18 Correct 1445 ms 91092 KB Output is correct
19 Correct 999 ms 81656 KB Output is correct
20 Correct 1503 ms 81528 KB Output is correct

Subtask #4
0 / 17.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 Execution timed out 4058 ms 3576 KB Time limit exceeded
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 Execution timed out 4026 ms 384 KB Time limit exceeded
4 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 Execution timed out 4086 ms 384 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.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 Execution timed out 4059 ms 384 KB Time limit exceeded
5 Halted 0 ms 0 KB -