# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
541507 | 2022-03-23T17:09:46 Z | AmirElarbi | Jousting tournament (IOI12_tournament) | C++14 | 1000 ms | 7244 KB |
#include <bits/stdc++.h> #define vi vector<int> #define ve vector #define ll long long #define vf vector<float> #define vll vector<pair<ll,ll>> #define ii pair<int,int> #define pll pair<ll,ll> #define vvi vector<vi> #define vii vector<ii> #define gii greater<ii> #define pb push_back #define mp make_pair #define fi first #define se second #define INF 2e9+5 #define eps 1e-7 #define eps1 1e-25 #define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); #define MAX_A 1e5+5 #define V 450 using namespace std; const int MOD = 1e9; const int nax = 1e5+5; int st[nax][30]; int lg[nax+1]; int GetBestPosition(int n, int c, int r, int *k, int *s, int *e) { vi rngs(n); for (int i = 0; i < n; ++i) rngs[i] = i; for (int i = 0; i < c; ++i) { int lb = lower_bound(rngs.begin(), rngs.end(), s[i])-rngs.begin(); int ub = upper_bound(rngs.begin(), rngs.end(), e[i])-rngs.begin()-1; for (int j = lb; j <= ub; ++j) rngs[j] = rngs[lb]; for (int j = ub+1; j < n; ++j) rngs[j] -= (e[i]-s[i]); s[i] = lb,e[i] = ub; } int mx = 0, ps = 0; lg[1] = 0; for (int i = 2; i < nax; i++) lg[i] = lg[i/2] + 1; for (int i = 0; i < n-1; i++) st[i][0] = k[i]; for (int j = 1; j < 30; j++) for (int i = 0; i + (1 << j) <= n; i++) st[i][j] = max(st[i][j-1], st[i + (1 << (j - 1))][j - 1]); for (int i = 0; i < n; ++i) { int res = 0, ind = i; for (int j = 0; j < c; ++j) { if(s[j] <= i && i <= e[j]){ int clg = lg[e[j] - s[j] ]; int cur = max(st[s[j]][clg], st[e[j] - (1 << clg)][clg]); if(cur < r) res++; else break; } } if(res > mx){ mx = res; ps = i; } } return ps; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 596 KB | Output is correct |
2 | Correct | 1 ms | 596 KB | Output is correct |
3 | Correct | 1 ms | 724 KB | Output is correct |
4 | Correct | 1 ms | 724 KB | Output is correct |
5 | Correct | 1 ms | 724 KB | Output is correct |
6 | Correct | 1 ms | 724 KB | Output is correct |
7 | Correct | 1 ms | 724 KB | Output is correct |
8 | Correct | 1 ms | 724 KB | Output is correct |
9 | Correct | 1 ms | 724 KB | Output is correct |
10 | Correct | 1 ms | 724 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 724 KB | Output is correct |
2 | Correct | 23 ms | 1364 KB | Output is correct |
3 | Correct | 4 ms | 1236 KB | Output is correct |
4 | Correct | 21 ms | 1364 KB | Output is correct |
5 | Correct | 22 ms | 1364 KB | Output is correct |
6 | Correct | 42 ms | 1352 KB | Output is correct |
7 | Correct | 31 ms | 1348 KB | Output is correct |
8 | Correct | 22 ms | 1364 KB | Output is correct |
9 | Correct | 1 ms | 1236 KB | Output is correct |
10 | Correct | 43 ms | 1348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1095 ms | 7244 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |