oj.uz

Submission #542621

# Submission time Handle Problem Language Result Execution time Memory
542621 2022-03-27T08:15:25 Z alextodoran Jousting tournament (IOI12_tournament) C++17
100 / 100
 78 ms 8404 KB 
/**
 ____ ____ ____ ____ ____
||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

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 596 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 3 ms 568 KB Output is correct
5 Correct 4 ms 564 KB Output is correct
6 Correct 3 ms 568 KB Output is correct
7 Correct 3 ms 564 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 4 ms 640 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3740 KB Output is correct
2 Correct 69 ms 8404 KB Output is correct
3 Correct 25 ms 4900 KB Output is correct
4 Correct 78 ms 8344 KB Output is correct
5 Correct 53 ms 8112 KB Output is correct
6 Correct 62 ms 7244 KB Output is correct
7 Correct 56 ms 8344 KB Output is correct
8 Correct 58 ms 8348 KB Output is correct
9 Correct 20 ms 4672 KB Output is correct
10 Correct 28 ms 4952 KB Output is correct