Submission #431878

#	Time	Username	Problem	Language	Result	Execution time	Memory
431878		TryMax	Comparing Plants (IOI20_plants)	C++17	27 / 100	637 ms	11956 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
#ifdef LOCAL
    #include "grader.cpp"
#endif // LOCAL

#define f first
#define s second

using namespace std;

const int N = 2e5 + 10, inf = 1e9 + 10;

int was[N], w[4 * N], n1;
pair<int, int> t[4 * N];
vector<int> a, p;

void push(int u){
    t[2 * u + 1].f += w[u];
    t[2 * u + 2].f += w[u];
    w[2 * u + 1] += w[u];
    w[2 * u + 2] += w[u];
    w[u] = 0;
}

pair<int, int> cmp(pair<int, int> a, pair<int, int> b){
    if(a.f > b.f)
        return a;
    else if(a.f < b.f)
        return b;
    else if(a.s < b.s)
        return a;
    else
        return b;
}

void upd(int u, int tl, int tr, int l, int r, int val){
    if(l <= tl && tr <= r){
        t[u].f += val;
        w[u] += val;
        if(tl == tr)
            t[u].s = tl;
        return;
    }
    push(u);
    int tm = (tl + tr) / 2;
    if(l <= tm)
        upd(2 * u + 1, tl, tm, l, r, val);
    if(r >= tm + 1)
        upd(2 * u + 2, tm + 1, tr, l, r, val);
    t[u] = cmp(t[2 * u + 1], t[2 * u + 2]);
}

pair<int, int> get(int u, int tl, int tr, int l, int r){
//    cout << u << " " << tl << " " << tr << " " << endl;
    if(l <= tl && tr <= r)
        return t[u];
    push(u);
    int tm = (tl + tr) / 2;
    pair<int, int> res = {-inf, 0};
    if(l <= tm)
        res = cmp(res, get(2 * u + 1, tl, tm, l, r));
    if(r >= tm + 1)
        res = cmp(res, get(2 * u + 2, tm + 1, tr, l, r));
    return res;
}

pair<int, int> get_lr(int l, int r){
    if(l <= r)
        return get(0, 0, n1 - 1, l, r);
    else
        return cmp(get(0, 0, n1 - 1, 0, r), get(0, 0, n1 - 1, l, n1 - 1));
}

void upd_lr(int l, int r){
    if(l <= r)
        upd(0, 0, n1 - 1, l, r, 1);
    else{
        upd(0, 0, n1 - 1, 0, r, 1);
        upd(0, 0, n1 - 1, l, n1 - 1, 1);
    }
}

void init(int K, vector<int> r) {
    int k;
    k = K;
    a = r;
    n1 = a.size();
    p.resize(n1);
    for(int j = 0; j < n1; ++j){
        a[j] = k - 1 - a[j];
        upd(0, 0, n1 - 1, j, j, a[j]);
    }
    for(int i = n1 - 1; i >= 0; --i){
//        cout << i << endl;
        int pos = get_lr(0, n1 - 1).s;
//        cout << pos << endl;
//        cout << i << endl;
        pair<int, int> nxt = get_lr((pos + k) % n1, (pos - 1 + n1) % n1);
        if(nxt.f == k - 1)
            pos = nxt.s;
        p[pos] = i;
        upd(0, 0, n1 - 1, pos, pos, -inf);
        upd_lr((pos - k + 1 + n1) % n1, pos);
//        for(int i = 0; i < n; ++i)
//            cout << p[i] << " ";
//        cout << endl;
    }
}

int compare_plants(int x, int y) {
    if(p[x] > p[y])
        return 1;
    else
        return -1;
}
/*
4 3 2
0 1 1 2
0 2
1 2

1
-1

5 3 3
2 2 0 0 0
0 2
1 2
2 4
*/

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