oj.uz

답안 #810050

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
810050 2023-08-06T04:44:28 Z PixelCat 식물 비교 (IOI20_plants) C++14
30 / 100
 1060 ms 96312 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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 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 2 ms 6996 KB Output is correct
5 Correct 3 ms 6996 KB Output is correct
6 Correct 63 ms 9740 KB Output is correct
7 Correct 137 ms 17376 KB Output is correct
8 Correct 862 ms 86852 KB Output is correct
9 Correct 851 ms 86472 KB Output is correct
10 Correct 770 ms 86652 KB Output is correct
11 Correct 915 ms 87768 KB Output is correct
12 Correct 974 ms 87300 KB Output is correct
13 Correct 1039 ms 96312 KB Output is correct
14 Correct 508 ms 77524 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 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 7016 KB Output is correct
5 Correct 3 ms 6996 KB Output is correct
6 Correct 6 ms 7396 KB Output is correct
7 Correct 60 ms 11512 KB Output is correct
8 Correct 4 ms 7124 KB Output is correct
9 Correct 5 ms 7380 KB Output is correct
10 Correct 74 ms 11540 KB Output is correct
11 Correct 99 ms 11720 KB Output is correct
12 Correct 82 ms 11644 KB Output is correct
13 Correct 58 ms 11624 KB Output is correct

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 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 7016 KB Output is correct
5 Correct 3 ms 6996 KB Output is correct
6 Correct 6 ms 7396 KB Output is correct
7 Correct 60 ms 11512 KB Output is correct
8 Correct 4 ms 7124 KB Output is correct
9 Correct 5 ms 7380 KB Output is correct
10 Correct 74 ms 11540 KB Output is correct
11 Correct 99 ms 11720 KB Output is correct
12 Correct 82 ms 11644 KB Output is correct
13 Correct 58 ms 11624 KB Output is correct
14 Correct 93 ms 16704 KB Output is correct
15 Incorrect 891 ms 77516 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 6996 KB Output is correct
2 Correct 3 ms 6996 KB Output is correct
3 Correct 87 ms 10524 KB Output is correct
4 Correct 753 ms 83704 KB Output is correct
5 Correct 883 ms 78828 KB Output is correct
6 Correct 1060 ms 77556 KB Output is correct
7 Correct 894 ms 77444 KB Output is correct
8 Incorrect 865 ms 77448 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 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 4 ms 7124 KB Output is correct
7 Correct 20 ms 8080 KB Output is correct
8 Correct 18 ms 8064 KB Output is correct
9 Correct 24 ms 7988 KB Output is correct
10 Correct 16 ms 7992 KB Output is correct
11 Correct 22 ms 7976 KB Output is correct
12 Correct 23 ms 8008 KB Output is correct
13 Correct 18 ms 8100 KB Output is correct

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 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 6 ms 7388 KB Output is correct
6 Correct 656 ms 79900 KB Output is correct
7 Correct 687 ms 79880 KB Output is correct
8 Correct 704 ms 80104 KB Output is correct
9 Incorrect 739 ms 80272 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 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 2 ms 6996 KB Output is correct
5 Correct 3 ms 6996 KB Output is correct
6 Correct 63 ms 9740 KB Output is correct
7 Correct 137 ms 17376 KB Output is correct
8 Correct 862 ms 86852 KB Output is correct
9 Correct 851 ms 86472 KB Output is correct
10 Correct 770 ms 86652 KB Output is correct
11 Correct 915 ms 87768 KB Output is correct
12 Correct 974 ms 87300 KB Output is correct
13 Correct 1039 ms 96312 KB Output is correct
14 Correct 508 ms 77524 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 4 ms 7016 KB Output is correct
19 Correct 3 ms 6996 KB Output is correct
20 Correct 6 ms 7396 KB Output is correct
21 Correct 60 ms 11512 KB Output is correct
22 Correct 4 ms 7124 KB Output is correct
23 Correct 5 ms 7380 KB Output is correct
24 Correct 74 ms 11540 KB Output is correct
25 Correct 99 ms 11720 KB Output is correct
26 Correct 82 ms 11644 KB Output is correct
27 Correct 58 ms 11624 KB Output is correct
28 Correct 93 ms 16704 KB Output is correct
29 Incorrect 891 ms 77516 KB Output isn't correct
30 Halted 0 ms 0 KB -