Submission #768861

#	Time	Username	Problem	Language	Result	Execution time	Memory
768861		keta_tsimakuridze	Jousting tournament (IOI12_tournament)	C++14	0 / 100	88 ms	6812 KiB

tournament

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n;
int lz[4 * N], t[4 * N], fw[N];
void upd(int u, int id, int l, int r) {
    if(l > id || r < id) return;
    if(l == r) {
        t[u] ^= 1;
        return;
    }
    int mid = (l + r) / 2;
    upd(2 * u, id, l, mid); upd(2 * u + 1, id, mid + 1, r);
    t[u] = t[2 * u] + t[2 * u + 1];
}
int get(int u, int l, int r, int id) {
    if(l == r) return l;
    int mid = (l + r) / 2;
    if(t[2 * u] >= id) return get(2 * u, l, mid, id);
    return get(2 * u + 1, mid + 1, r, id - t[2 * u]);
}
void upd(int id, int v) {
    ++id;
    for(id; id <= n; id += id & (-id)) fw[id] += v;
}
int get(int id) {
    int ans = 0; ++id;
    for(id; id >= 1; id -= id & (-id)) ans += fw[id];
    return ans;
}
int GetBestPosition(int nn, int C, int R, int *K, int *ST, int *E) {
    set<int> s, S, bad;
    n = nn;
    for(int i = 0; i < n; i++) s.insert(i), S.insert(i), upd(1, i, 0, n - 1);
    for(int i = 0; i < n - 1; i++) {
        if(K[i] > R) bad.insert(i);
    }
    bad.insert(n + 1); s.insert(n + 1); S.insert(n + 1);
    int ans = 0;
    for(int i = 0; i < C; i++) {
        ST[i] = (ST[i] == 0 ? 0 : get(1, 0, n - 1, ST[i]) + 1); E[i] = get(1, 0, n - 1, E[i] + 1);;
        while(*s.upper_bound(ST[i] - 1) <= E[i]) {
            int x = *s.upper_bound(ST[i] - 1);
            s.erase(x);
            upd(1, x, 0, n - 1);
        }
        upd(1, E[i], 0, n - 1); s.insert(E[i]);

        if(*bad.upper_bound(ST[i] - 1) >= E[i]) upd(ST[i], 1), upd(E[i] + 1, -1);
        else {
            while(*S.upper_bound(ST[i] - 1) <= E[i]) {
                ans = max(ans, get(*S.upper_bound(ST[i] - 1)));
                S.erase(*S.upper_bound(ST[i] - 1));
            }
        }
    }
    while(S.size()) ans = max(ans, get(*S.begin())), S.erase(*S.begin());
    return ans;
}

Compilation message (stderr)

tournament.cpp: In function 'void upd(int, int)':
tournament.cpp:24:9: warning: statement has no effect [-Wunused-value]
   24 |     for(id; id <= n; id += id & (-id)) fw[id] += v;
      |         ^~
tournament.cpp: In function 'int get(int)':
tournament.cpp:28:9: warning: statement has no effect [-Wunused-value]
   28 |     for(id; id >= 1; id -= id & (-id)) ans += fw[id];
      |         ^~

• Subtask 1: 0 / 17
• Subtask 2: 0 / 32
• Subtask 3: 0 / 51