oj.uz

Submission #790622

# Submission time Handle Problem Language Result Execution time Memory
790622 2023-07-23T02:05:50 Z resting Comparing Plants (IOI20_plants) C++17
44 / 100
 1157 ms 122408 KB 
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;

#define time fuck

const int mx = 2e5 + 5;

int n, k;
struct segtree {
    int l, r, lz = 0, mn = 0;
    segtree* lc = 0, * rc = 0;
    segtree* getmem();
    segtree() : segtree(-1, -1) {};
    segtree(int l, int r) : l(l), r(r) {
        if (l == r)return;
        int m = (l + r) / 2;
        lc = getmem(); *lc = segtree(l, m);
        rc = getmem(); *rc = segtree(m + 1, r);
    }
    void apply(int v) {
        mn += v; lz += v;
    }
    void push() {
        if (l == r) return;
        lc->apply(lz);rc->apply(lz);
        lz = 0;
    }
    void pull() {
        if (l == r) return;
        mn = min(lc->mn, rc->mn);
    }
    void upd(int ql, int qr, int qv) {
        if (qr < 0) { ql += n; qr += n; }
        if (ql < 0) {
            upd(0, qr, qv);
            upd((n)+ql, (n - 1), qv);
            return;
        }
        if (ql >= n) { ql -= n; qr -= n; }
        if (qr >= n) {
            upd(ql, (n - 1), qv);
            upd(0, qr - (n), qv);
            return;
        }
        if (l > qr || r < ql) return;
        if (ql <= l && r <= qr) { apply(qv); return; }
        push();
        lc->upd(ql, qr, qv);
        rc->upd(ql, qr, qv);
        pull();
    }
    int extract_min() {
        if (l == r) return l;
        push();
        if (lc->mn == mn) return lc->extract_min();
        return rc->extract_min();
    }
}mem[mx * 8]; int memsz = 0;
segtree* segtree::getmem() { return &mem[memsz++]; }

const int inf = 1e9 + 7;
namespace rmq {
    struct segtree {
        int l, r, lz = 0;
        segtree* lc = 0, * rc = 0;
        pair<int, int> v = { 0, -1 };
        segtree* getmem();
        segtree() : segtree(-1, -1) {};
        segtree(int l, int r) : l(l), r(r) {
            if (l == r)return;
            int m = (l + r) / 2;
            lc = getmem(); *lc = segtree(l, m);
            rc = getmem(); *rc = segtree(m + 1, r);
        }
        void upd(int qi, int qv) {
            if (l == r) { v = { qv, qi };return; }
            if (qi <= lc->r) lc->upd(qi, qv);
            else rc->upd(qi, qv);
            v = min(lc->v, rc->v);
        }
        pair<int, int> q(int ql, int qr) {
            if (qr < 0) { ql += n; qr += n; }
            if (ql < 0) {
                return min(q(0, qr), q((n)+ql, (n - 1)));
            }
            if (ql >= n) { ql -= n; qr -= n; }
            if (qr >= n) {
                return min(q(ql, (n - 1)), q(0, qr - (n)));
            }
            if (l > qr || r < ql)return { 0, -1 };
            if (ql <= l && r <= qr) return v;
            return min(lc->q(ql, qr), rc->q(ql, qr));
        }
    }mem[mx * 4]; int memsz = 0;
    segtree* segtree::getmem() { return &mem[memsz++]; }
}


vector<int> time, rtime;
int parl[mx][20], parr[mx][20];
void init(int kk, std::vector<int> r) {
    n = r.size();k = kk;k--;
    time = rtime = vector<int>(n, 0);
    segtree parta(0, n - 1), partb(0, n - 1); partb.upd(0, n - 1, 1);
    for (int i = 0; i < n; i++) parta.upd(i, i, r[i]);
    for (int i = 0; i < n; i++) {
        while (parta.mn == 0) {
            int t = parta.extract_min();
            parta.upd(t, t, mx);
            partb.upd(t, t, -1);
            partb.upd(t + 1, t + k, 1);
        }
        int t = partb.extract_min();
        time[t] = i;
        rtime[i] = t;
        partb.upd(t, t, mx);
        partb.upd(t + 1, t + k, -1);
        parta.upd(t - k, t, -1);
    }
    rmq::segtree tim(0, n - 1);
    for (int i = 0; i < n; i++) {
        int t = tim.q(rtime[i] - k, rtime[i]).second;
        if (t == -1) parl[rtime[i]][0] = rtime[i];
        else parl[rtime[i]][0] = t;
        t = tim.q(rtime[i], rtime[i] + k).second;
        if (t == -1) parr[rtime[i]][0] = rtime[i];
        else parr[rtime[i]][0] = t;
    }
    for (int i = 1; i < 20; i++) {
        for (int j = 0; j < n; j++) {
            if (parl[j][0] > j) parl[j][i] = parl[j][i - 1];
            else if (parl[parl[j][i - 1]][i - 1] > j) parl[j][i] = parl[j][i - 1];
            else parl[j][i] = parl[parl[j][i - 1]][i - 1];
        }
    }
    for (int i = 1; i < 20; i++) {
        for (int j = 0; j < n; j++) {
            if (parr[j][0] < j) parr[j][i] = parr[j][i - 1];
            else if (parr[parr[j][i - 1]][i - 1] < j) parr[j][i] = parr[j][i - 1];
            else parr[j][i] = parr[parr[j][i - 1]][i - 1];

        }
    }
    return;
}

int compare_plants(int x, int y) {
    //compare zero
    if (x + k >= y || y + k - n >= x) { return time[x] < time[y] ? 1 : -1; }

    //compare one
    int t = x;
    for (int i = 19; i >= 0; i--) {
        if (parr[t][i] + k < y) t = parr[t][i];
    }
    t = parr[t][0];
    if (t + k >= y && time[t] > time[y]) return -1;

    //compare two
    t = parl[x][19];
    if (y + k - n >= t && time[y] < time[t]) return -1;
    t = parl[t][0];
    for (int i = 19; i >= 0; i--) {
        if (y + k < parl[t][i]) t = parl[t][i];
    }
    t = parl[t][0];
    if (y + k >= t && time[y] < time[t])return -1;

    //compare three
    t = y;
    for (int i = 19; i >= 0; i--) {
        if (x + k < parl[t][i]) t = parl[t][i];
    }
    t = parl[t][0];
    if (x + k >= t && time[t] > time[x]) return 1;

    //compare four
    t = parr[y][19];
    if (t + k - n >= x && time[t] > time[x]) return 1;
    t = parr[t][0];
    for (int i = 19; i >= 0; i--) {
        if (parr[t][i] + k < x) t = parr[t][i];
    }
    t = parr[t][0];
    if (t + k >= x && time[t] > time[x]) return 1;
    return 0;
}

// int main() {
//     init(3, { 0, 1, 1, 2 });
//     cout << compare_plants(0, 2) << endl;
//     cout << compare_plants(1, 2) << endl;
// }

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 81620 KB Output is correct
2 Correct 34 ms 81620 KB Output is correct
3 Correct 34 ms 81632 KB Output is correct
4 Incorrect 33 ms 81680 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 81664 KB Output is correct
2 Correct 34 ms 81712 KB Output is correct
3 Correct 34 ms 81664 KB Output is correct
4 Correct 34 ms 81696 KB Output is correct
5 Correct 36 ms 81680 KB Output is correct
6 Correct 37 ms 81920 KB Output is correct
7 Correct 86 ms 87268 KB Output is correct
8 Correct 35 ms 81740 KB Output is correct
9 Correct 37 ms 82000 KB Output is correct
10 Correct 86 ms 87272 KB Output is correct
11 Correct 83 ms 87176 KB Output is correct
12 Correct 87 ms 87372 KB Output is correct
13 Correct 87 ms 87212 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 81664 KB Output is correct
2 Correct 34 ms 81712 KB Output is correct
3 Correct 34 ms 81664 KB Output is correct
4 Correct 34 ms 81696 KB Output is correct
5 Correct 36 ms 81680 KB Output is correct
6 Correct 37 ms 81920 KB Output is correct
7 Correct 86 ms 87268 KB Output is correct
8 Correct 35 ms 81740 KB Output is correct
9 Correct 37 ms 82000 KB Output is correct
10 Correct 86 ms 87272 KB Output is correct
11 Correct 83 ms 87176 KB Output is correct
12 Correct 87 ms 87372 KB Output is correct
13 Correct 87 ms 87212 KB Output is correct
14 Correct 131 ms 90140 KB Output is correct
15 Correct 1122 ms 122232 KB Output is correct
16 Correct 140 ms 90128 KB Output is correct
17 Correct 1105 ms 122152 KB Output is correct
18 Correct 652 ms 121840 KB Output is correct
19 Correct 689 ms 122352 KB Output is correct
20 Correct 932 ms 122408 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 81612 KB Output is correct
2 Correct 40 ms 81700 KB Output is correct
3 Correct 120 ms 86612 KB Output is correct
4 Correct 638 ms 121348 KB Output is correct
5 Correct 715 ms 121492 KB Output is correct
6 Correct 1038 ms 121792 KB Output is correct
7 Correct 1157 ms 121948 KB Output is correct
8 Correct 1137 ms 122244 KB Output is correct
9 Correct 685 ms 121420 KB Output is correct
10 Correct 698 ms 121532 KB Output is correct
11 Correct 620 ms 121368 KB Output is correct
12 Correct 641 ms 121572 KB Output is correct
13 Correct 705 ms 121708 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 81616 KB Output is correct
2 Correct 38 ms 81700 KB Output is correct
3 Incorrect 34 ms 81688 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 81628 KB Output is correct
2 Correct 35 ms 81652 KB Output is correct
3 Incorrect 35 ms 81608 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 81620 KB Output is correct
2 Correct 34 ms 81620 KB Output is correct
3 Correct 34 ms 81632 KB Output is correct
4 Incorrect 33 ms 81680 KB Output isn't correct
5 Halted 0 ms 0 KB -