oj.uz

Submission #790678

# Submission time Handle Problem Language Result Execution time Memory
790678 2023-07-23T05:23:55 Z resting Comparing Plants (IOI20_plants) C++17
43 / 100
 1109 ms 116028 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;
        segtree* lc = 0, * rc = 0;
        pair<int, int> v = { -1, -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 = max(lc->v, rc->v);
        }
        pair<int, int> q(int ql, int qr) {
            if (qr < 0) { ql += n; qr += n; }
            if (ql < 0) {
                return max(q(0, qr), q((n)+ql, (n - 1)));
            }
            if (ql >= n) { ql -= n; qr -= n; }
            if (qr >= n) {
                return max(q(ql, (n - 1)), q(0, qr - (n)));
            }
            if (l > qr || r < ql)return { -1, -1 };
            if (ql <= l && r <= qr) return v;
            return max(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];

int cheat[500][500]{} ;
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;
        //   cout << "#" << t << endl;
        t = tim.q(rtime[i], rtime[i] + k).second;
        // cout << "#" << t << endl;
        if (t == -1) parr[rtime[i]][0] = rtime[i];
        else parr[rtime[i]][0] = t;
        tim.upd(rtime[i], i);
    }
    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];

        }
    }

    if (n <= 300) {
        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= k; j++) {
                int j2 = (i + j) % n;
                if (time[j2] < time[i]) cheat[i][j2] = 1;
                else cheat[j2][i] = 1;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int x = 0; x < n; x++) {
                for (int y = 0; y < n; y++) {
                    cheat[x][y] |= cheat[x][i] && cheat[i][y];
                }
            }
        }
    }
    return;
}

int compare_plants(int x, int y) {
    if (n <= 300) {
        if (cheat[x][y]) return -1;
        if(cheat[y][x])return 1;
        return 0;
    }
    //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[t] > time[y]) return -1;
    if (t != parl[t][0]) {
        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[t] > time[y])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;
    if (t != parr[t][0]) {
        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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 75340 KB Output is correct
2 Correct 32 ms 75444 KB Output is correct
3 Correct 31 ms 75476 KB Output is correct
4 Correct 31 ms 75560 KB Output is correct
5 Correct 30 ms 75468 KB Output is correct
6 Correct 70 ms 79292 KB Output is correct
7 Correct 137 ms 83864 KB Output is correct
8 Correct 574 ms 115188 KB Output is correct
9 Correct 603 ms 115068 KB Output is correct
10 Correct 588 ms 115148 KB Output is correct
11 Correct 607 ms 115088 KB Output is correct
12 Correct 606 ms 115128 KB Output is correct
13 Correct 649 ms 115096 KB Output is correct
14 Correct 641 ms 115160 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 75372 KB Output is correct
2 Correct 33 ms 75344 KB Output is correct
3 Correct 29 ms 75396 KB Output is correct
4 Correct 30 ms 75396 KB Output is correct
5 Correct 31 ms 75552 KB Output is correct
6 Correct 34 ms 75716 KB Output is correct
7 Correct 90 ms 81008 KB Output is correct
8 Correct 38 ms 75660 KB Output is correct
9 Correct 33 ms 75660 KB Output is correct
10 Correct 83 ms 81048 KB Output is correct
11 Correct 83 ms 80880 KB Output is correct
12 Correct 80 ms 81136 KB Output is correct
13 Correct 88 ms 81112 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 75372 KB Output is correct
2 Correct 33 ms 75344 KB Output is correct
3 Correct 29 ms 75396 KB Output is correct
4 Correct 30 ms 75396 KB Output is correct
5 Correct 31 ms 75552 KB Output is correct
6 Correct 34 ms 75716 KB Output is correct
7 Correct 90 ms 81008 KB Output is correct
8 Correct 38 ms 75660 KB Output is correct
9 Correct 33 ms 75660 KB Output is correct
10 Correct 83 ms 81048 KB Output is correct
11 Correct 83 ms 80880 KB Output is correct
12 Correct 80 ms 81136 KB Output is correct
13 Correct 88 ms 81112 KB Output is correct
14 Correct 132 ms 83920 KB Output is correct
15 Correct 1109 ms 115916 KB Output is correct
16 Correct 133 ms 83964 KB Output is correct
17 Correct 1088 ms 115968 KB Output is correct
18 Correct 662 ms 115428 KB Output is correct
19 Correct 687 ms 115948 KB Output is correct
20 Correct 991 ms 116028 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 75444 KB Output is correct
2 Correct 30 ms 75448 KB Output is correct
3 Incorrect 105 ms 78620 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 75452 KB Output is correct
2 Correct 34 ms 75372 KB Output is correct
3 Correct 30 ms 75360 KB Output is correct
4 Correct 30 ms 75464 KB Output is correct
5 Correct 32 ms 75428 KB Output is correct
6 Correct 32 ms 75668 KB Output is correct
7 Correct 65 ms 76948 KB Output is correct
8 Correct 72 ms 77004 KB Output is correct
9 Correct 67 ms 76988 KB Output is correct
10 Correct 72 ms 76988 KB Output is correct
11 Correct 66 ms 77028 KB Output is correct
12 Correct 67 ms 77060 KB Output is correct
13 Correct 73 ms 76940 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 75476 KB Output is correct
2 Correct 31 ms 75448 KB Output is correct
3 Correct 31 ms 75444 KB Output is correct
4 Correct 32 ms 75392 KB Output is correct
5 Incorrect 33 ms 75580 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 75340 KB Output is correct
2 Correct 32 ms 75444 KB Output is correct
3 Correct 31 ms 75476 KB Output is correct
4 Correct 31 ms 75560 KB Output is correct
5 Correct 30 ms 75468 KB Output is correct
6 Correct 70 ms 79292 KB Output is correct
7 Correct 137 ms 83864 KB Output is correct
8 Correct 574 ms 115188 KB Output is correct
9 Correct 603 ms 115068 KB Output is correct
10 Correct 588 ms 115148 KB Output is correct
11 Correct 607 ms 115088 KB Output is correct
12 Correct 606 ms 115128 KB Output is correct
13 Correct 649 ms 115096 KB Output is correct
14 Correct 641 ms 115160 KB Output is correct
15 Correct 28 ms 75372 KB Output is correct
16 Correct 33 ms 75344 KB Output is correct
17 Correct 29 ms 75396 KB Output is correct
18 Correct 30 ms 75396 KB Output is correct
19 Correct 31 ms 75552 KB Output is correct
20 Correct 34 ms 75716 KB Output is correct
21 Correct 90 ms 81008 KB Output is correct
22 Correct 38 ms 75660 KB Output is correct
23 Correct 33 ms 75660 KB Output is correct
24 Correct 83 ms 81048 KB Output is correct
25 Correct 83 ms 80880 KB Output is correct
26 Correct 80 ms 81136 KB Output is correct
27 Correct 88 ms 81112 KB Output is correct
28 Correct 132 ms 83920 KB Output is correct
29 Correct 1109 ms 115916 KB Output is correct
30 Correct 133 ms 83964 KB Output is correct
31 Correct 1088 ms 115968 KB Output is correct
32 Correct 662 ms 115428 KB Output is correct
33 Correct 687 ms 115948 KB Output is correct
34 Correct 991 ms 116028 KB Output is correct
35 Correct 31 ms 75444 KB Output is correct
36 Correct 30 ms 75448 KB Output is correct
37 Incorrect 105 ms 78620 KB Output isn't correct
38 Halted 0 ms 0 KB -