Submission #1043724

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043724		Sharky	Jousting tournament (IOI12_tournament)	C++17	100 / 100	73 ms	10192 KiB

tournament

#include <bits/stdc++.h>
using namespace std;

const int N = 100008;

struct Fenwick {
    int fen[N];

    void upd(int i, int k) {
        for (; i < N; i += (i & -i)) fen[i] += k;
    }

    int query(int i) {
        int res = 0;
        for (; i; i -= (i & -i)) res += fen[i];
        return res;
    }
} love, hate;

int GetBestPosition(int n, int k, int rk, int *tmp, int *lb, int *rb) {
    vector<int> S(k), E(k);
    vector<vector<int>> rng(n+1);
    vector<int> a(n+1), nxt(n+1, n), lst(n+1, 0), diff(n+1, 0);
    for (int i = 1; i <= n; i++) {
        if (i < n) a[i] = tmp[i - 1];
        love.upd(i, 1);
        hate.upd(i, 1);
    }
    for (int i = 0; i < k; i++) {
        vector<int> g, h;
        lb[i]++, rb[i]++;
        for (int j = lb[i]; j <= rb[i]; j++) {
            int l = 1, r = n;
            while (l < r) {
                int mid = (l + r) >> 1;
                if (love.query(mid) >= j) r = mid;
                else l = mid + 1;
            }
            g.push_back(l);
            l = 1, r = n;
            while (l < r) {
                int mid = (l + r) >> 1;
                if (hate.query(mid) >= j) r = mid;
                else l = mid + 1;
            }
            h.push_back(l);
        }
        S[i] = g.front();
        E[i] = h.back();
        rng[S[i]].push_back(E[i]);
        for (int j = 1; j < (int) g.size(); j++) love.upd(g[j], -1);
        for (int j = 0; j < (int) g.size() - 1; j++) hate.upd(h[j], -1);
    }
    for (int i = n - 1; i >= 1; i--) {
        if (a[i] > rk) nxt[i] = i;
        else nxt[i] = nxt[i + 1];
    }
    for (int i = 1; i <= n - 1; i++) {
        if (a[i] > rk) lst[i] = i;
        else lst[i] = lst[i - 1];
    }
    int prv = -1, mx = -1, ans;
    for (int i = 1; i <= n; i++) {
        int l = lst[i - 1] + 1, r = nxt[i];
        if (l != prv) {
            for (int j = l; j <= r; j++) {
                for (auto x : rng[j]) {
                    if (x <= r) {
                        diff[j]++;
                        diff[x+1]--;
                    }
                }
            }
            for (int j = l+1; j <= r+1; j++) diff[j] += diff[j - 1];
            prv = l;
        }
        if (diff[i] > mx) mx = diff[i], ans = i;
    }
    return ans - 1;
}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:79:18: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   79 |     return ans - 1;
      |                  ^

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