oj.uz

Submission #308010

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

    {
        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 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 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 97 ms 3224 KB Output is correct
7 Correct 237 ms 11896 KB Output is correct
8 Correct 1002 ms 90864 KB Output is correct
9 Correct 1056 ms 90480 KB Output is correct
10 Correct 1343 ms 90480 KB Output is correct
11 Correct 3159 ms 91568 KB Output is correct
12 Execution timed out 4082 ms 91120 KB Time limit exceeded
13 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 1 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 107 ms 5316 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 5 ms 896 KB Output is correct
10 Correct 102 ms 5368 KB Output is correct
11 Correct 131 ms 5496 KB Output is correct
12 Correct 98 ms 5368 KB Output is correct
13 Correct 101 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 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 5 ms 896 KB Output is correct
7 Correct 107 ms 5316 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 5 ms 896 KB Output is correct
10 Correct 102 ms 5368 KB Output is correct
11 Correct 131 ms 5496 KB Output is correct
12 Correct 98 ms 5368 KB Output is correct
13 Correct 101 ms 5368 KB Output is correct
14 Correct 196 ms 11572 KB Output is correct
15 Correct 1644 ms 81448 KB Output is correct
16 Correct 197 ms 11592 KB Output is correct
17 Correct 1634 ms 81400 KB Output is correct
18 Correct 1398 ms 91160 KB Output is correct
19 Correct 960 ms 81400 KB Output is correct
20 Correct 1467 ms 81448 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Incorrect 169 ms 4216 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 3 ms 512 KB Output is correct
7 Incorrect 26 ms 1152 KB Output isn't correct
8 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 768 KB Output is correct
6 Incorrect 1343 ms 81784 KB Output isn't correct
7 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 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 97 ms 3224 KB Output is correct
7 Correct 237 ms 11896 KB Output is correct
8 Correct 1002 ms 90864 KB Output is correct
9 Correct 1056 ms 90480 KB Output is correct
10 Correct 1343 ms 90480 KB Output is correct
11 Correct 3159 ms 91568 KB Output is correct
12 Execution timed out 4082 ms 91120 KB Time limit exceeded
13 Halted 0 ms 0 KB -