Submission #800293

#	Time	Username	Problem	Language	Result	Execution time	Memory
800293		PixelCat	Comparing Plants (IOI20_plants)	C++14	0 / 100	28 ms	5244 KiB

plants

#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 = 300;

int n, k;
int rk[MAXN + 10];

int dist(int s, int t) {
    if(s <= t) return t - s;
    else return t - s + n;
}

#define L(id) ((id) * 2 + 1)
#define R(id) ((id) * 2 + 2)
struct SegTree {
    int add[MAXN * 4 + 10];
    pii mn[MAXN * 4 + 10];  // {index, value}
    pii comp(pii a, pii b) {
        if(a.S < b.S) return a;
        if(b.S < a.S) return b;
        if(dist(a.F, b.F) < k) return a;
        return b;
    }
    void pull(int id) {
        mn[id] = comp(mn[L(id)], mn[R(id)]);
        mn[id].S += add[id];
    }
    void build(int id, int l, int r, vector<int> &owo) {
        add[id] = 0;
        if(l == r) {
            mn[id] = pii(l, 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(id, l, r, L, n - 1, val);
            range_add(id, l, r, 0, R, val);
            return;
        }
        if(l >= L && r <= R) {
            add[id] += val;
            mn[id].S += 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);
    }
} seg;

void init(int __k, vector<int> r) {
    k = __k;
    n = sz(r);
    vector<int> alive(n, 1);
    seg.build(0, 0, n - 1, r);
    For(rank, 1, n) {
        int idx = seg.mn[0].F;
        // cerr << idx << "\n";
        // For(i, 0, n - 1) cerr << r[i] << " \n"[i == n - 1];
        seg.range_add(0, 0, n - 1, (idx + n - k + 1) % n, (idx + n - 1) % n, -1);
        seg.range_add(0, 0, n - 1, idx, idx, n * 888);
        alive[idx] = 0;
        rk[idx] = rank;
    }
}

int compare_plants(int x, int y) {
    if(rk[x] < rk[y]) return 1;
    return -1;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25