Submission #44237

#TimeUsernameProblemLanguageResultExecution timeMemory
44237baactreeJousting tournament (IOI12_tournament)C++17
0 / 100
28 ms4144 KiB
#include <bits/stdc++.h> using namespace std; int par[100005], sz[100005], tree[100005]; int ssz, mtree[400005]; int find(int x) { if (x == par[x])return x; return par[x] = find(par[x]); } void merge(int x, int y) { x = find(x); y = find(y); if (x == y)return; par[x] = y; sz[y] += sz[x]; } void update(int idx, int val) { idx++; while (idx < 100005) { tree[idx] += val; idx += idx & (-idx); } } int query(int idx) { int ret = 0; idx++; while (idx) { ret += tree[idx]; idx -= idx & (-idx); } return ret; } void mupdate(int idx, int val) { idx += ssz; while (idx) { mtree[idx] = max(mtree[idx], val); idx /= 2; } } int mquery(int le, int ri) { le += ssz; ri += ssz; int ret = 0; while (le <= ri) { if (le & 1)ret = max(ret, mtree[le++]); if (!(ri & 1))ret = max(ret, mtree[ri--]); le /= 2; ri /= 2; } return ret; } int s[100005], e[100005]; int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) { for (int i = 0; i < N; i++) { par[i] = i; sz[i] = 1; if(i) update(i, 1); } for (int i = 0; i < C; i++) { int pre = -1; int le, ri, mid, st; le = 0; ri = N - 1; st = 0; while (le <= ri) { mid = (le + ri) / 2; if (query(mid) >= S[i]) { st = mid; ri = mid - 1; } else le = mid + 1; } s[i] = st; for (int j = S[i]; j <= E[i]; j++) { int ss = sz[find(st)]; e[i] = st + ss - 1; if (pre != -1)merge(pre, st); pre = st; st += ss; } } ssz = 1; while (ssz < N)ssz *= 2; for (int i = 0; i < N - 1; i++) mupdate(i, K[i]); mupdate(N - 1, 0x3f3f3f3f); vector<pair<int, int> > vec; for (int i = 0; i < C; i++) { if (mquery(s[i] + 1, e[i]) < R ||mquery(s[i], e[i] - 1) < R) vec.emplace_back(s[i], e[i]); } sort(vec.begin(), vec.end(), [](pair<int, int> a, pair<int, int> b) { if (a.second == b.second) { return a.first < b.first; } return a.second > b.second; }); vector<int> lis; int ans = 0; int idx = 0; for (int i = 0; i < vec.size(); i++) { auto it = upper_bound(lis.begin(), lis.end(), vec[i].first); if (it == lis.end()) { lis.push_back(vec[i].first); ans = lis.size(); idx = vec[i].first; } else { *it = vec[i].first; int len = it - lis.begin() + 1; if (ans < len || (ans == len && idx > vec[i].first)) { ans = len; idx = vec[i].first; } } } return idx; }

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:100:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vec.size(); i++) {
                  ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...