Submission #1043716

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043716		Sharky	Jousting tournament (IOI12_tournament)	C++17	0 / 100	23 ms	4444 KiB

tournament

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

const int N = 100008;

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;
}

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];
        upd(i, 1);
    }
    for (int i = 0; i < k; i++) {
        vector<int> g;
        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 (query(mid) >= j) r = mid;
                else l = mid + 1;
            }
            g.push_back(l);
        }
        S[i] = g.front();
        E[i] = g.back();
        rng[S[i]].push_back(E[i]);
        for (int j = 1; j < (int) g.size(); j++) upd(g[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; 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:68:18: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   68 |     return ans - 1;
      |                  ^

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