#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
typedef vector<int> vi;
#define mp make_pair
#define f first
#define s second
#define sz(x) (int)x.size()
#define ins insert
#define lb lower_bound
#define pb push_back
template<class T> bool ckmax(T& a, const T& b) {
return a < b ? a = b, 1 : 0; }
/**
* Description: A set (not multiset!) with support for finding the $n$'th
* element, and finding the index of an element. Change \texttt{null\_type} for map.
* Time: O(\log N)
* Source: KACTL
* Verification: many
*/
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>,
rb_tree_tag, tree_order_statistics_node_update>;
#define ook order_of_key
#define fbo find_by_order
void treeExample() {
Tree<int> t, t2; t.insert(8);
auto it = t.insert(10).f; assert(it == t.lb(9));
assert(t.ook(10) == 1 && t.ook(11) == 2 && *t.fbo(0) == 8);
t.join(t2); // assuming T < T2 or T > T2, merge t2 into t
}
/**
int atMost(Tree<pi>& T, int r) {
return T.ook({r,MOD}); }
int getSum(Tree<pi>& T, int l, int r) {
return atMost(T,r)-atMost(T,l-1); }
*/
pi topi[200005];
int par[200005][30];
int curind = 0;
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
pi ans = mp(-1, -N);
for(int i = 0; i < N; i++){
vi curranks;
int ind = 0;
for(int j = 0; j <= N-1; j++){
if(j == i) curranks.pb(R);
else curranks.pb(K[ind++]);
}
int curans = 0;
for(int j = 0; j < C; j++){
vi newranks;
bool isin = 0;
int maxval = -1;
for(int i = 0; i < sz(curranks); i++){
if(S[j] <= i && i <= E[j]){
if(curranks[i] == R){
isin = 1;
}
ckmax(maxval, curranks[i]);
if(i == E[j]){
newranks.pb(maxval);
}
continue;
}
newranks.pb(curranks[i]);
}
swap(curranks, newranks);
if(isin == 1 && maxval != R){
break;
}
if(isin == 1) curans++;
}
//cout << i << " " << curans << "\n";
ckmax(ans, mp(curans, -i));
}
return -ans.s;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
9 ms |
384 KB |
Output is correct |
3 |
Correct |
232 ms |
384 KB |
Output is correct |
4 |
Correct |
208 ms |
384 KB |
Output is correct |
5 |
Correct |
29 ms |
376 KB |
Output is correct |
6 |
Correct |
217 ms |
384 KB |
Output is correct |
7 |
Correct |
212 ms |
384 KB |
Output is correct |
8 |
Correct |
203 ms |
384 KB |
Output is correct |
9 |
Correct |
8 ms |
384 KB |
Output is correct |
10 |
Correct |
33 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1068 ms |
504 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1092 ms |
1776 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |