oj.uz

답안 #809560

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
809560 2023-08-06T02:17:39 Z PixelCat 식물 비교 (IOI20_plants) C++14
44 / 100
 448 ms 30736 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 rk[MAXN + 10];
 
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];
    int mn[MAXN * 4 + 10];
    void pull(int id) {
        mn[id] = min(mn[L(id)], mn[R(id)]) + add[id];
    }
    void build(int id, int l, int r, vector<int> &owo) {
        add[id] = 0;
        if(l == r) {
            add[id] = mn[id] = owo[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] += 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);
    }
    int kill_min(int id, int l, int r, int accu) {
        accu += add[id];
        if(l == r) {
            if(accu == 0) {
                add[id] = mn[id] = n * 888;
                return l;
            }
            return -1;
        }
        int m = (l + r) / 2;
        int res;
        if(mn[L(id)] < mn[R(id)]) {
            res = kill_min(L(id), l, m, accu);
        } else {
            res = kill_min(R(id), m + 1, r, accu);
        }
        pull(id);
        return res;
    }
    void kill() {
        int res = kill_min(0, 0, n - 1, 0);
        while(res != -1) {
            aya.insert(res);
            res = kill_min(0, 0, n - 1, 0);
        }
    }
} seg;
 
void init(int __k, vector<int> r) {
    k = __k;
    n = sz(r);
    seg.build(0, 0, n - 1, r);
    seg.kill();
    For(rank, 1, n) {
        // aya.out();
        int idx = aya.pop();
        // aya.out();
        // cerr << idx << "\n\n";
        seg.range_add(0, 0, n - 1, (idx + n - k + 1) % n, (idx + n - 1) % n, -1);
        seg.kill();
        rk[idx] = rank;
    }
}
 
int compare_plants(int x, int y) {
    if(rk[x] < rk[y]) return 1;
    return -1;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 44 ms 3308 KB Output is correct
8 Correct 1 ms 352 KB Output is correct
9 Correct 2 ms 352 KB Output is correct
10 Correct 53 ms 3356 KB Output is correct
11 Correct 55 ms 3516 KB Output is correct
12 Correct 47 ms 3476 KB Output is correct
13 Correct 43 ms 3340 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 44 ms 3308 KB Output is correct
8 Correct 1 ms 352 KB Output is correct
9 Correct 2 ms 352 KB Output is correct
10 Correct 53 ms 3356 KB Output is correct
11 Correct 55 ms 3516 KB Output is correct
12 Correct 47 ms 3476 KB Output is correct
13 Correct 43 ms 3340 KB Output is correct
14 Correct 67 ms 3828 KB Output is correct
15 Correct 292 ms 9128 KB Output is correct
16 Correct 75 ms 6068 KB Output is correct
17 Correct 288 ms 12896 KB Output is correct
18 Correct 448 ms 21780 KB Output is correct
19 Correct 212 ms 12840 KB Output is correct
20 Correct 227 ms 12900 KB Output is correct

Subtask #4
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 48 ms 3236 KB Output is correct
4 Correct 294 ms 15384 KB Output is correct
5 Correct 296 ms 13596 KB Output is correct
6 Correct 302 ms 12516 KB Output is correct
7 Correct 312 ms 12604 KB Output is correct
8 Correct 362 ms 12780 KB Output is correct
9 Correct 304 ms 16764 KB Output is correct
10 Correct 287 ms 13696 KB Output is correct
11 Correct 349 ms 30736 KB Output is correct
12 Correct 180 ms 12156 KB Output is correct
13 Correct 388 ms 25288 KB Output is correct

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -