# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
428975 | 2021-06-15T16:00:31 Z | wiwiho | Jousting tournament (IOI12_tournament) | C++14 | 189 ms | 11900 KB |
#include <bits/stdc++.h> #include <bits/extc++.h> #define mp make_pair #define F first #define S second #define eb emplace_back #define iter(a) a.begin(), a.end() #define lsort(a) sort(iter(a)) #define uni(a) a.resize(unique(iter(a))); #define printv(a, b) { \ for(auto pv : a) b << pv << " "; \ b << "\n"; \ } using namespace std; typedef long long ll; using pii = pair<int, int>; using tree = __gnu_pbds::tree<int, __gnu_pbds::null_type, less<>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>; const ll MOD = 1000000000; int GetBestPosition(int n, int m, int R, int *K, int *S, int *E) { vector<int> pos; for(int i = 0; i < n - 1; i++){ if(K[i] > R) pos.eb(i); } tree tr; for(int i = 0; i <= n; i++) tr.insert(i); vector<pii> ev; vector<bool> kill(m); for(int i = 0; i < m; i++){ auto lit = tr.find_by_order(S[i]); auto rit = tr.find_by_order(E[i]); S[i] = *lit; E[i] = *next(rit) - 1; for(auto it = next(lit); *it <= E[i]; it = tr.erase(it)); ev.eb(mp(S[i], i + 1)); ev.eb(mp(E[i] + 1, -i - 1)); auto it = lower_bound(iter(pos), S[i]); kill[i] = it != pos.end() && *it < E[i]; } lsort(ev); tree now; set<int> ks; int ep = 0; int ans = 0, ansp = 0; for(int i = 0; i < n; i++){ while(ep < ev.size() && ev[ep].F <= i){ if(ev[ep].S > 0){ int id = ev[ep].S - 1; now.insert(id); if(kill[id]) ks.insert(id); } else{ int id = -ev[ep].S - 1; now.erase(id); ks.erase(id); } ep++; } int tans; if(ks.empty()) tans = now.size(); else tans = now.order_of_key(*ks.begin()); if(tans > ans){ ans = tans; ansp = i; } } return ansp; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | Output is correct |
2 | Correct | 1 ms | 296 KB | Output is correct |
3 | Correct | 2 ms | 332 KB | Output is correct |
4 | Correct | 1 ms | 332 KB | Output is correct |
5 | Correct | 1 ms | 204 KB | Output is correct |
6 | Correct | 1 ms | 332 KB | Output is correct |
7 | Correct | 1 ms | 304 KB | Output is correct |
8 | Correct | 1 ms | 332 KB | Output is correct |
9 | Correct | 1 ms | 204 KB | Output is correct |
10 | Correct | 1 ms | 204 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 332 KB | Output is correct |
2 | Correct | 7 ms | 816 KB | Output is correct |
3 | Correct | 3 ms | 588 KB | Output is correct |
4 | Correct | 7 ms | 844 KB | Output is correct |
5 | Correct | 7 ms | 664 KB | Output is correct |
6 | Correct | 6 ms | 716 KB | Output is correct |
7 | Correct | 8 ms | 684 KB | Output is correct |
8 | Correct | 7 ms | 844 KB | Output is correct |
9 | Correct | 3 ms | 584 KB | Output is correct |
10 | Correct | 8 ms | 824 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 74 ms | 4296 KB | Output is correct |
2 | Correct | 185 ms | 11900 KB | Output is correct |
3 | Correct | 89 ms | 6280 KB | Output is correct |
4 | Correct | 175 ms | 10128 KB | Output is correct |
5 | Correct | 172 ms | 9584 KB | Output is correct |
6 | Correct | 164 ms | 8228 KB | Output is correct |
7 | Correct | 178 ms | 10168 KB | Output is correct |
8 | Correct | 189 ms | 9656 KB | Output is correct |
9 | Correct | 83 ms | 6276 KB | Output is correct |
10 | Correct | 86 ms | 6344 KB | Output is correct |