Submission #431852

#	Time	Username	Problem	Language	Result	Execution time	Memory
431852		TryMax	Comparing Plants (IOI20_plants)	C++17	Compilation error	0 ms	0 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 = 1e5 + 10, inf = 1e9 + 10;

int was[N], w[4 * N];
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;
}

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] = max(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 = max(res, get(2 * u + 1, tl, tm, l, r));
    if(r >= tm + 1)
        res = max(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, n - 1, l, r);
    else
        return max(get(0, 0, n - 1, 0, r), get(0, 0, n - 1, l, n - 1));
}

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

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

Compilation message (stderr)

plants.cpp: In function 'std::pair<int, int> get_lr(int, int)':
plants.cpp:59:26: error: 'n' was not declared in this scope
   59 |         return get(0, 0, n - 1, l, r);
      |                          ^
plants.cpp:61:30: error: 'n' was not declared in this scope
   61 |         return max(get(0, 0, n - 1, 0, r), get(0, 0, n - 1, l, n - 1));
      |                              ^
plants.cpp: In function 'void upd_lr(int, int)':
plants.cpp:66:19: error: 'n' was not declared in this scope
   66 |         upd(0, 0, n - 1, l, r, 1);
      |                   ^
plants.cpp:68:19: error: 'n' was not declared in this scope
   68 |         upd(0, 0, n - 1, 0, r, 1);
      |                   ^