oj.uz

Submission #810086

# Submission time Handle Problem Language Result Execution time Memory
810086 2023-08-06T04:51:48 Z PixelCat Comparing Plants (IOI20_plants) C++14
30 / 100
 1186 ms 96212 KB 
#include "plants.h"
 
#ifdef NYAOWO
#include "grader.cpp"
#endif
 
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
// #define int LL
using namespace std;
using i32 = int32_t;
using LL = long long;
using pii = pair<int, int>;
 
const int MAXN = 200'000;
const int MAXLG = 20;
 
int n, k;
 
int dist(int s, int t) {
    if(s <= t) return t - s;
    else return t - s + n;
}

struct Ayaya {
    set<int> pos;
    set<pii> d;
    pii find(int x) {
        auto itr = pos.upper_bound(x);
        if(itr == pos.end()) {
            itr = pos.begin();
        }
        auto itl = pos.lower_bound(x);
        if(itl == pos.begin()) {
            itl = prev(pos.end());
        } else {
            itl = prev(itl);
        }
        return pii(*itl, *itr);
    }
    void insert(int x) {
        if(sz(pos) == 0) {
            pos.insert(x);
            d.emplace(0, x);
            return;
        }
        int l, r; tie(l, r) = find(x);
        d.erase(pii(dist(l, r), r));
        d.insert(pii(dist(l, x), x));
        d.insert(pii(dist(x, r), r));
        pos.insert(x);
    }
    void erase(int x) {
        if(sz(pos) == 1) {
            pos.clear(); d.clear();
            return;
        }
        int l, r; tie(l, r) = find(x);
        d.erase(pii(dist(l, x), x));
        d.erase(pii(dist(x, r), r));
        d.insert(pii(dist(l, r), r));
        pos.erase(x);
    }
    int pop() {
        int i = prev(d.end())->S;
        erase(i);
        return i;
    }
    void out() {
        for(auto &i:pos) cerr << i << " ";
        cerr << "\n";
        for(auto &i:d) cerr << "(" << i.F << ", " << i.S << ") ";
        cerr << "\n";
    }
} aya;

#define L(id) ((id) * 2 + 1)
#define R(id) ((id) * 2 + 2)
struct SegTree {
    int add[MAXN * 4 + 10];
    pii mn[MAXN * 4 + 10];  // {value, index}
    void pull(int id) {
        mn[id] = min(mn[L(id)], mn[R(id)]);
        mn[id].F += add[id];
    }
    void build(int id, int l, int r, int *owo) {
        add[id] = 0;
        if(l == r) {
            add[id] = owo[l];
            mn[id] = pii(owo[l], l);
            return;
        }
        int m = (l + r) / 2;
        build(L(id), l, m, owo);
        build(R(id), m + 1, r, owo);
        pull(id);
    }
    void range_add(int id, int l, int r, int L, int R, int val) {
        if(L > R) {
            range_add(0, 0, n - 1, L, n - 1, val);
            range_add(0, 0, n - 1, 0, R, val);
            return;
        }
        if(l >= L && r <= R) {
            add[id] += val; mn[id].F += val;
            return;
        }
        int m = (l + r) / 2;
        if(L <= m) range_add(L(id), l, m, L, R, val);
        if(R > m)  range_add(R(id), m + 1, r, L, R, val);
        pull(id);
    }
    pii find_min(int id, int l, int r, int L, int R) {
        if(L > R) {
            return min(
                find_min(0, 0, n - 1, L, n - 1),
                find_min(0, 0, n - 1, 0, R)
            );
        }
        if(l >= L && r <= R) return mn[id];
        int m = (l + r) / 2;
        pii res(n * 8, -1);
        if(L <= m) res = min(res, find_min(L(id), l, m, L, R));
        if(R > m)  res = min(res, find_min(R(id), m + 1, r, L, R));
        res.F += add[id];
        return res;
    }
    void kill_all() {
        pii res = find_min(0, 0, n - 1, 0, n - 1);
        while(res.F == 0) {
            aya.insert(res.S);
            range_add(0, 0, n - 1, res.S, res.S, n * 888);
            res = find_min(0, 0, n - 1, 0, n - 1);
        }
    }
} seg;

int r[MAXN + 10];
int rk[MAXN + 10];
int pos[MAXN + 10];
int pl[MAXLG + 10][MAXN + 10];
int pr[MAXLG + 10][MAXN + 10];
int sl[MAXLG + 10][MAXN + 10];
int sr[MAXLG + 10][MAXN + 10];

void init(int __k, vector<int> __r) {
    k = __k;
    n = sz(__r);
    For(i, 0, n - 1) r[i] = __r[i];
    
    seg.build(0, 0, n - 1, r);
    seg.kill_all();
    For(rank, 1, n) {
        int idx = aya.pop();
        seg.range_add(0, 0, n - 1, (idx + n - k + 1) % n, (idx + n - 1) % n, -1);
        seg.kill_all();
        rk[idx] = rank;
        pos[rank] = idx;
    }

    seg.build(0, 0, n - 1, rk);
    For(rank, 1, n) {
        int idx = pos[rank];
        pii owo;
        owo = seg.find_min(0, 0, n - 1, (idx + n - k + 1) % n, (idx + n - 1) % n);
        pl[0][idx] = (owo.F <= n ? owo.S : idx);
        owo = seg.find_min(0, 0, n - 1, (idx + 1) % n, (idx + k - 1) % n);
        pr[0][idx] = (owo.F <= n ? owo.S : idx);
        sl[0][idx] = dist(pl[0][idx], idx);
        sr[0][idx] = dist(idx, pr[0][idx]);
        seg.range_add(0, 0, n - 1, idx, idx, n * 888);
    }

    // For(i, 0, n - 1) cerr << rk[i] << " \n"[i == n - 1];
    // For(i, 0, n - 1) cerr << pl[i] << " \n"[i == n - 1];
    // For(i, 0, n - 1) cerr << sl[i] << " \n"[i == n - 1];
    // For(i, 0, n - 1) cerr << pr[i] << " \n"[i == n - 1];
    // For(i, 0, n - 1) cerr << sr[i] << " \n"[i == n - 1];
    
    For(j, 1, MAXLG - 1) {
        For(i, 0, n - 1) {
            pl[j][i] = pl[j - 1][pl[j - 1][i]];
            pr[j][i] = pr[j - 1][pr[j - 1][i]];
            sl[j][i] = sl[j - 1][i] + sl[j - 1][pl[j - 1][i]];
            sr[j][i] = sr[j - 1][i] + sr[j - 1][pr[j - 1][i]];
        }
        // For(i, 0, n - 1) cerr << sr[i] << " \n"[i == n - 1];
    }
}
 
int compare_plants(int x, int y) {
    if(rk[x] > rk[y]) return -compare_plants(y, x);

    int d, x2;
    // left
    d = dist(y, x);
    x2 = x;
    Forr(i, MAXLG - 1, 0) {
        if(d - sl[i][x2] > 0) {
            d -= sl[i][x2];
            x2 = pl[i][x2];
        }
    }
    if(d <= sl[0][x2] && rk[x2] <= rk[y]) return 1;
    // right
    d = dist(x, y);
    x2 = x;
    Forr(i, MAXLG - 1, 0) {
        if(d - sr[i][x2] > 0) {
            d -= sr[i][x2];
            x2 = pr[i][x2];
        }
    }
    if(d <= sr[0][x2] && rk[x2] <= rk[y]) return 1;

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6996 KB Output is correct
2 Correct 2 ms 6996 KB Output is correct
3 Correct 2 ms 6996 KB Output is correct
4 Correct 3 ms 6996 KB Output is correct
5 Correct 2 ms 6996 KB Output is correct
6 Correct 57 ms 9752 KB Output is correct
7 Correct 135 ms 17328 KB Output is correct
8 Correct 965 ms 86836 KB Output is correct
9 Correct 1014 ms 86488 KB Output is correct
10 Correct 916 ms 86728 KB Output is correct
11 Correct 1086 ms 87700 KB Output is correct
12 Correct 980 ms 87324 KB Output is correct
13 Correct 1186 ms 96212 KB Output is correct
14 Correct 520 ms 77516 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6996 KB Output is correct
2 Correct 3 ms 6996 KB Output is correct
3 Correct 3 ms 6996 KB Output is correct
4 Correct 3 ms 6996 KB Output is correct
5 Correct 3 ms 6996 KB Output is correct
6 Correct 5 ms 7380 KB Output is correct
7 Correct 60 ms 11524 KB Output is correct
8 Correct 4 ms 7124 KB Output is correct
9 Correct 6 ms 7380 KB Output is correct
10 Correct 59 ms 11636 KB Output is correct
11 Correct 95 ms 11740 KB Output is correct
12 Correct 95 ms 11640 KB Output is correct
13 Correct 63 ms 11508 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6996 KB Output is correct
2 Correct 3 ms 6996 KB Output is correct
3 Correct 3 ms 6996 KB Output is correct
4 Correct 3 ms 6996 KB Output is correct
5 Correct 3 ms 6996 KB Output is correct
6 Correct 5 ms 7380 KB Output is correct
7 Correct 60 ms 11524 KB Output is correct
8 Correct 4 ms 7124 KB Output is correct
9 Correct 6 ms 7380 KB Output is correct
10 Correct 59 ms 11636 KB Output is correct
11 Correct 95 ms 11740 KB Output is correct
12 Correct 95 ms 11640 KB Output is correct
13 Correct 63 ms 11508 KB Output is correct
14 Correct 102 ms 16716 KB Output is correct
15 Incorrect 920 ms 77544 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7016 KB Output is correct
2 Correct 3 ms 6996 KB Output is correct
3 Correct 95 ms 10572 KB Output is correct
4 Correct 740 ms 83784 KB Output is correct
5 Correct 824 ms 78832 KB Output is correct
6 Correct 805 ms 77572 KB Output is correct
7 Correct 709 ms 77452 KB Output is correct
8 Incorrect 804 ms 77520 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6996 KB Output is correct
2 Correct 3 ms 6996 KB Output is correct
3 Correct 7 ms 6996 KB Output is correct
4 Correct 3 ms 6996 KB Output is correct
5 Correct 3 ms 6968 KB Output is correct
6 Correct 4 ms 7124 KB Output is correct
7 Correct 21 ms 7764 KB Output is correct
8 Correct 14 ms 7740 KB Output is correct
9 Correct 19 ms 7744 KB Output is correct
10 Correct 14 ms 7672 KB Output is correct
11 Correct 17 ms 7752 KB Output is correct
12 Correct 18 ms 7668 KB Output is correct
13 Correct 16 ms 7764 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6996 KB Output is correct
2 Correct 3 ms 6996 KB Output is correct
3 Correct 3 ms 6996 KB Output is correct
4 Correct 4 ms 6996 KB Output is correct
5 Correct 5 ms 7380 KB Output is correct
6 Correct 602 ms 77752 KB Output is correct
7 Correct 698 ms 77508 KB Output is correct
8 Correct 642 ms 77448 KB Output is correct
9 Incorrect 692 ms 77440 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6996 KB Output is correct
2 Correct 2 ms 6996 KB Output is correct
3 Correct 2 ms 6996 KB Output is correct
4 Correct 3 ms 6996 KB Output is correct
5 Correct 2 ms 6996 KB Output is correct
6 Correct 57 ms 9752 KB Output is correct
7 Correct 135 ms 17328 KB Output is correct
8 Correct 965 ms 86836 KB Output is correct
9 Correct 1014 ms 86488 KB Output is correct
10 Correct 916 ms 86728 KB Output is correct
11 Correct 1086 ms 87700 KB Output is correct
12 Correct 980 ms 87324 KB Output is correct
13 Correct 1186 ms 96212 KB Output is correct
14 Correct 520 ms 77516 KB Output is correct
15 Correct 3 ms 6996 KB Output is correct
16 Correct 3 ms 6996 KB Output is correct
17 Correct 3 ms 6996 KB Output is correct
18 Correct 3 ms 6996 KB Output is correct
19 Correct 3 ms 6996 KB Output is correct
20 Correct 5 ms 7380 KB Output is correct
21 Correct 60 ms 11524 KB Output is correct
22 Correct 4 ms 7124 KB Output is correct
23 Correct 6 ms 7380 KB Output is correct
24 Correct 59 ms 11636 KB Output is correct
25 Correct 95 ms 11740 KB Output is correct
26 Correct 95 ms 11640 KB Output is correct
27 Correct 63 ms 11508 KB Output is correct
28 Correct 102 ms 16716 KB Output is correct
29 Incorrect 920 ms 77544 KB Output isn't correct
30 Halted 0 ms 0 KB -