oj.uz

Submission #809983

# Submission time Handle Problem Language Result Execution time Memory
809983 2023-08-06T04:21:41 Z PixelCat Comparing Plants (IOI20_plants) C++14
19 / 100
 746 ms 39704 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;
 
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[MAXN + 10];
int pr[MAXN + 10];
int sl[MAXN + 10];
int sr[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[idx] = (owo.F <= n ? owo.S : idx);
        owo = seg.find_min(0, 0, n - 1, (idx + 1) % n, (idx + k - 1) % n);
        pr[idx] = (owo.F <= n ? owo.S : idx);
        sl[idx] = dist(pl[idx], idx);
        sr[idx] = dist(idx, pr[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(_, 1, 49) {
        For(rank, 1, n) {
            int idx = pos[rank];
            sl[idx] += sl[pl[idx]];
            pl[idx] = pl[pl[idx]];
            sr[idx] += sr[pr[idx]];
            pr[idx] = pr[pr[idx]];
        }
        // 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);
    bool uwu = false;
    if(sl[x] >= n - 1) uwu = true;
    if(sl[x] >= dist(y, x)) uwu = true;
    if(sr[x] >= dist(x, y)) uwu = true;
    return (uwu ? (rk[x] < rk[y] ? 1 : -1) : 0);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6576 KB Output is correct
2 Correct 4 ms 6612 KB Output is correct
3 Correct 3 ms 6572 KB Output is correct
4 Correct 4 ms 6612 KB Output is correct
5 Correct 3 ms 6564 KB Output is correct
6 Correct 44 ms 10284 KB Output is correct
7 Correct 75 ms 13144 KB Output is correct
8 Correct 474 ms 30204 KB Output is correct
9 Correct 434 ms 29932 KB Output is correct
10 Correct 414 ms 30012 KB Output is correct
11 Correct 487 ms 31172 KB Output is correct
12 Correct 460 ms 30728 KB Output is correct
13 Correct 518 ms 39704 KB Output is correct
14 Correct 256 ms 20924 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6612 KB Output is correct
2 Correct 4 ms 6572 KB Output is correct
3 Correct 3 ms 6612 KB Output is correct
4 Correct 3 ms 6612 KB Output is correct
5 Correct 3 ms 6612 KB Output is correct
6 Correct 5 ms 6712 KB Output is correct
7 Correct 56 ms 11480 KB Output is correct
8 Correct 4 ms 6680 KB Output is correct
9 Correct 6 ms 6708 KB Output is correct
10 Correct 59 ms 11492 KB Output is correct
11 Correct 71 ms 11688 KB Output is correct
12 Correct 50 ms 11604 KB Output is correct
13 Correct 62 ms 11468 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6612 KB Output is correct
2 Correct 4 ms 6572 KB Output is correct
3 Correct 3 ms 6612 KB Output is correct
4 Correct 3 ms 6612 KB Output is correct
5 Correct 3 ms 6612 KB Output is correct
6 Correct 5 ms 6712 KB Output is correct
7 Correct 56 ms 11480 KB Output is correct
8 Correct 4 ms 6680 KB Output is correct
9 Correct 6 ms 6708 KB Output is correct
10 Correct 59 ms 11492 KB Output is correct
11 Correct 71 ms 11688 KB Output is correct
12 Correct 50 ms 11604 KB Output is correct
13 Correct 62 ms 11468 KB Output is correct
14 Correct 94 ms 12528 KB Output is correct
15 Incorrect 746 ms 21728 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 6612 KB Output is correct
2 Correct 3 ms 6532 KB Output is correct
3 Correct 55 ms 11216 KB Output is correct
4 Correct 465 ms 27072 KB Output is correct
5 Correct 520 ms 22456 KB Output is correct
6 Correct 637 ms 21436 KB Output is correct
7 Correct 729 ms 21508 KB Output is correct
8 Incorrect 745 ms 21568 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6612 KB Output is correct
2 Correct 3 ms 6612 KB Output is correct
3 Correct 3 ms 6612 KB Output is correct
4 Correct 3 ms 6612 KB Output is correct
5 Incorrect 3 ms 6612 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6572 KB Output is correct
2 Correct 3 ms 6612 KB Output is correct
3 Correct 4 ms 6612 KB Output is correct
4 Correct 4 ms 6572 KB Output is correct
5 Incorrect 5 ms 6612 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6576 KB Output is correct
2 Correct 4 ms 6612 KB Output is correct
3 Correct 3 ms 6572 KB Output is correct
4 Correct 4 ms 6612 KB Output is correct
5 Correct 3 ms 6564 KB Output is correct
6 Correct 44 ms 10284 KB Output is correct
7 Correct 75 ms 13144 KB Output is correct
8 Correct 474 ms 30204 KB Output is correct
9 Correct 434 ms 29932 KB Output is correct
10 Correct 414 ms 30012 KB Output is correct
11 Correct 487 ms 31172 KB Output is correct
12 Correct 460 ms 30728 KB Output is correct
13 Correct 518 ms 39704 KB Output is correct
14 Correct 256 ms 20924 KB Output is correct
15 Correct 3 ms 6612 KB Output is correct
16 Correct 4 ms 6572 KB Output is correct
17 Correct 3 ms 6612 KB Output is correct
18 Correct 3 ms 6612 KB Output is correct
19 Correct 3 ms 6612 KB Output is correct
20 Correct 5 ms 6712 KB Output is correct
21 Correct 56 ms 11480 KB Output is correct
22 Correct 4 ms 6680 KB Output is correct
23 Correct 6 ms 6708 KB Output is correct
24 Correct 59 ms 11492 KB Output is correct
25 Correct 71 ms 11688 KB Output is correct
26 Correct 50 ms 11604 KB Output is correct
27 Correct 62 ms 11468 KB Output is correct
28 Correct 94 ms 12528 KB Output is correct
29 Incorrect 746 ms 21728 KB Output isn't correct
30 Halted 0 ms 0 KB -