Submission #945755

#TimeUsernameProblemLanguageResultExecution timeMemory
945755siewjhJousting tournament (IOI12_tournament)C++17
100 / 100
91 ms14168 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; int fw[MAXN], nums; void fupdate(int p, int v){ while (p <= nums){ fw[p] += v; p += (p & (-p)); } } int fquery(int p){ int ans = 0; while (p){ ans += fw[p]; p -= (p & (-p)); } return ans; } struct node{ int s, e, m, val; node *l, *r; node (int _s, int _e){ s = _s, e = _e, m = (s + e) >> 1, val = 0; if (s != e){ l = new node(s, m); r = new node(m + 1, e); } } void update(int p, int v){ if (s == e){ val = v; return; } else if (p <= m) l->update(p, v); else r->update(p, v); val = max(l->val, r->val); } int query(int x, int y){ if (x == s && y == e) return val; else if (y <= m) return l->query(x, y); else if (x > m) return r->query(x, y); else return max(l->query(x, m), r->query(m + 1, y)); } }; int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) { nums = N; set<int> spos; for (int i = 1; i <= nums; i++){ fupdate(i, 1); spos.insert(i); } spos.insert(nums + 1); vector<pair<int, int>> rcoords(C); for (int i = 0; i < C; i++){ int s = S[i], e = E[i], l = 1, r = nums, rs, re; s++; e++; while (l <= r){ int m = (l + r) >> 1; if (fquery(m) >= s){ rs = m; r = m - 1; } else l = m + 1; } auto it = spos.lower_bound(rs); it++; for (int j = s + 1; j <= e; j++, it = spos.erase(it)) fupdate(*it, -1); re = (*it) - 1; rcoords[i] = {rs, re}; } node *root = new node(1, nums - 1); for (int i = 1; i < nums; i++) root->update(i, K[i - 1]); vector<int> cumv(nums + 1); for (auto &[s, e] : rcoords) if (root->query(s, e - 1) < R){ cumv[s]++; cumv[e + 1]--; } int ans = -1, ind, curr = 0; for (int i = 1; i <= nums; i++){ curr += cumv[i]; if (curr > ans){ ans = curr; ind = i; } } return ind - 1; }

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:85:15: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
   85 |  return ind - 1;
      |               ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...