oj.uz

Submission #790623

# Submission time Handle Problem Language Result Execution time Memory
790623 2023-07-23T02:11:48 Z resting Comparing Plants (IOI20_plants) C++17
44 / 100
 1170 ms 118508 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;

    assert(false);
    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 81628 KB Output is correct
2 Correct 34 ms 81684 KB Output is correct
3 Correct 34 ms 81680 KB Output is correct
4 Incorrect 36 ms 81708 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 36 ms 81684 KB Output is correct
2 Correct 35 ms 81700 KB Output is correct
3 Correct 35 ms 81584 KB Output is correct
4 Correct 34 ms 81620 KB Output is correct
5 Correct 40 ms 81720 KB Output is correct
6 Correct 39 ms 81872 KB Output is correct
7 Correct 84 ms 85320 KB Output is correct
8 Correct 38 ms 81772 KB Output is correct
9 Correct 37 ms 81896 KB Output is correct
10 Correct 85 ms 85320 KB Output is correct
11 Correct 83 ms 85292 KB Output is correct
12 Correct 83 ms 85492 KB Output is correct
13 Correct 94 ms 85364 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 81684 KB Output is correct
2 Correct 35 ms 81700 KB Output is correct
3 Correct 35 ms 81584 KB Output is correct
4 Correct 34 ms 81620 KB Output is correct
5 Correct 40 ms 81720 KB Output is correct
6 Correct 39 ms 81872 KB Output is correct
7 Correct 84 ms 85320 KB Output is correct
8 Correct 38 ms 81772 KB Output is correct
9 Correct 37 ms 81896 KB Output is correct
10 Correct 85 ms 85320 KB Output is correct
11 Correct 83 ms 85292 KB Output is correct
12 Correct 83 ms 85492 KB Output is correct
13 Correct 94 ms 85364 KB Output is correct
14 Correct 133 ms 87980 KB Output is correct
15 Correct 1086 ms 118476 KB Output is correct
16 Correct 134 ms 87980 KB Output is correct
17 Correct 1124 ms 118468 KB Output is correct
18 Correct 683 ms 118476 KB Output is correct
19 Correct 708 ms 118492 KB Output is correct
20 Correct 959 ms 118476 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 81692 KB Output is correct
2 Correct 34 ms 81616 KB Output is correct
3 Correct 120 ms 84880 KB Output is correct
4 Correct 625 ms 118432 KB Output is correct
5 Correct 719 ms 118428 KB Output is correct
6 Correct 1058 ms 118476 KB Output is correct
7 Correct 1170 ms 118508 KB Output is correct
8 Correct 1123 ms 118436 KB Output is correct
9 Correct 663 ms 118508 KB Output is correct
10 Correct 675 ms 118476 KB Output is correct
11 Correct 592 ms 118404 KB Output is correct
12 Correct 628 ms 118404 KB Output is correct
13 Correct 714 ms 118432 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 81620 KB Output is correct
2 Correct 34 ms 81696 KB Output is correct
3 Incorrect 33 ms 81676 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 81676 KB Output is correct
2 Correct 35 ms 81652 KB Output is correct
3 Incorrect 35 ms 81612 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 81628 KB Output is correct
2 Correct 34 ms 81684 KB Output is correct
3 Correct 34 ms 81680 KB Output is correct
4 Incorrect 36 ms 81708 KB Output isn't correct
5 Halted 0 ms 0 KB -