oj.uz

Submission #308009

# Submission time Handle Problem Language Result Execution time Memory
308009 2020-09-29T18:08:39 Z VEGAnn Comparing Plants (IOI20_plants) C++17
25 / 100
 4000 ms 91888 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;

    // lf

    {
        int loc = x;

        while (1){
            int dst = loc - y;

            if (dst < 0) dst += n;

            if (dst < k) break;

            if (nt[0][loc] == loc) break;

            loc = nt[0][loc];
        }

        int dst = loc - y;

        if (dst < 0) dst += n;

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

    // rt

    {
        int loc = x;

        while (1){
            int dst = y - loc;

            if (dst < 0) dst += n;

            if (dst < k) break;

            if (nt[1][loc] == loc) break;

            loc = nt[1][loc];
        }

        int 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
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 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 65 ms 3320 KB Output is correct
7 Correct 229 ms 11892 KB Output is correct
8 Correct 941 ms 90608 KB Output is correct
9 Correct 1006 ms 90420 KB Output is correct
10 Correct 1669 ms 90680 KB Output is correct
11 Execution timed out 4098 ms 91888 KB Time limit exceeded
12 Halted 0 ms 0 KB -

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 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 5 ms 896 KB Output is correct
7 Correct 121 ms 5324 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 5 ms 896 KB Output is correct
10 Correct 89 ms 5368 KB Output is correct
11 Correct 665 ms 5624 KB Output is correct
12 Correct 94 ms 5572 KB Output is correct
13 Correct 86 ms 5368 KB Output is correct

Subtask #3
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 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 5 ms 896 KB Output is correct
7 Correct 121 ms 5324 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 5 ms 896 KB Output is correct
10 Correct 89 ms 5368 KB Output is correct
11 Correct 665 ms 5624 KB Output is correct
12 Correct 94 ms 5572 KB Output is correct
13 Correct 86 ms 5368 KB Output is correct
14 Correct 175 ms 11512 KB Output is correct
15 Correct 1605 ms 81512 KB Output is correct
16 Correct 173 ms 11512 KB Output is correct
17 Correct 1612 ms 81400 KB Output is correct
18 Execution timed out 4077 ms 91324 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 346 ms 4088 KB Output is correct
4 Execution timed out 4067 ms 87792 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
11.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 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 3 ms 512 KB Output is correct
7 Correct 19 ms 1152 KB Output is correct
8 Correct 18 ms 1152 KB Output is correct
9 Correct 27 ms 1144 KB Output is correct
10 Correct 18 ms 1152 KB Output is correct
11 Correct 22 ms 1152 KB Output is correct
12 Correct 21 ms 1144 KB Output is correct
13 Correct 15 ms 1152 KB Output is correct

Subtask #6
0 / 15.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 Correct 0 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 Correct 1483 ms 81784 KB Output is correct
7 Correct 1940 ms 81528 KB Output is correct
8 Correct 1677 ms 81596 KB Output is correct
9 Correct 1590 ms 81384 KB Output is correct
10 Execution timed out 4061 ms 86432 KB Time limit exceeded
11 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 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 65 ms 3320 KB Output is correct
7 Correct 229 ms 11892 KB Output is correct
8 Correct 941 ms 90608 KB Output is correct
9 Correct 1006 ms 90420 KB Output is correct
10 Correct 1669 ms 90680 KB Output is correct
11 Execution timed out 4098 ms 91888 KB Time limit exceeded
12 Halted 0 ms 0 KB -