Submission #542621

#	Time	Username	Problem	Language	Result	Execution time	Memory
542621		alextodoran	Jousting tournament (IOI12_tournament)	C++17	100 / 100	78 ms	8404 KiB

tournament

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Fenwick {
    vector <int> seg;
    Fenwick (int N) {
        seg = vector <int> (N, 0);
    }
    void update (int pos, int val) {
        for (int i = pos + 1; i <= (int) seg.size(); i += i & -i) {
            seg[i - 1] += val;
        }
    }
    void update (int l, int r, int val) {
        update(l, val);
        update(r + 1, -val);
    }
    int query (int pos) {
        int sum = 0;
        for (int i = pos + 1; i >= 1; i -= i & -i) {
            sum += seg[i - 1];
        }
        return sum;
    }
    int kth (int k) {
        k++;
        int bits = 32 - __builtin_clz((int) seg.size());
        int pos = -1;
        for (int step = (1 << bits); step >= 1; step >>= 1) {
            if (pos + step < (int) seg.size() && seg[pos + step] < k) {
                pos += step;
                k -= seg[pos];
            }
        }
        pos++; k--;
        return (k == 0 ? pos : (int) seg.size());
    }
};

int GetBestPosition (int N, int C, int X, int *K, int *L, int *R) {
    Fenwick lefts(N);
    for (int i = 0; i < N; i++) {
        lefts.update(i, +1);
    }
    for (int t = 0; t < C; t++) {
        int l = lefts.kth(L[t]), r = lefts.kth(R[t] + 1) - 1;
        for (int i = R[t]; i > L[t]; i--) {
            lefts.update(lefts.kth(i), -1);
        }
        L[t] = l; R[t] = r;
    }
    vector <int> rightOn[N];
    for (int t = 0; t < C; t++) {
        rightOn[R[t]].push_back(t);
    }
    int cmp[N];
    cmp[0] = -1;
    for (int i = 1; i < N; i++) {
        cmp[i] = (K[i - 1] < X ? -1 : +1);
    }
    Fenwick wins(N);
    vector <int> curr;
    int lastBetter = -1;
    int bestPos, maxWins = INT_MIN;
    for (int i = 0; i < N; i++) {
        if (cmp[i] == -1) {
            for (int t : rightOn[i]) {
                if (lastBetter < L[t]) {
                    curr.push_back(t);
                    wins.update(L[t], R[t], +1);
                }
            }
        } else {
            for (int j = lastBetter + 1; j < i; j++) {
                int maxHere = wins.query(j);
                if (maxHere > maxWins) {
                    maxWins = maxHere;
                    bestPos = j;
                }
            }
            while (curr.empty() == false) {
                int t = curr.back();
                wins.update(L[t], R[t], -1);
                curr.pop_back();
            }
            lastBetter = i - 1;
        }
    }
    return bestPos;
}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:100:12: warning: 'bestPos' may be used uninitialized in this function [-Wmaybe-uninitialized]
  100 |     return bestPos;
      |            ^~~~~~~

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