제출 #544316

#제출 시각아이디문제언어결과실행 시간메모리
544316sliviu마상시합 토너먼트 (IOI12_tournament)C++17
0 / 100
13 ms3580 KiB
#include <bits/stdc++.h> using namespace std; int GetBestPosition(int n, int m, int r, int* k, int* s, int* e) { int sol = 0; vector<int> bit(n + 2), win(n + 1), link(n + 1), ans(n + 1); auto update = [&](int pos, int val) { for (++pos; pos <= n + 1; pos += pos & -pos) bit[pos] += val; }; auto query = [&](int val) { int pos = 0, s = 0; for (int i = 31 - __builtin_ctz(n + 1); i >= 0; --i) if (pos + (1 << i) < n + 1 && s + bit[pos + (1 << i)] < val) pos += 1 << i, s += bit[pos]; return pos; }; for (int i = 0; i < n; ++i) { link[i] = i + 1; win[i + 1] = win[i] + k[i] > r; update(i, 1); } for (int i = 0; i < m; ++i) { int l = query(s[i] + 1), r = query(e[i] + 2); for (int j = link[l], next; j != r; j = next) { update(j, -1); next = link[j]; link[j] = r; } link[l] = r; if (!(win[r - 1] - win[l])) ++ans[l], --ans[r - 1]; } for (int i = 1; i < n; ++i) { ans[i] += ans[i - 1]; if (ans[i] > ans[sol]) sol = i; } return sol; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...