//#include "grader.cpp"
#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(),(a).end()
#define SZ(a) (int)(a).size()
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PLL;
typedef pair<int,int> PII;
typedef double D;
typedef long double LD;
const int N = 100003;
int p[N], fw[N], seg[N<<2], n, Rank, dp[N], L[N], R[N];
int* num;
set< pair<PII, int> > interval;
set< pair<PII, int> >::iterator it, it2;
vector<int> g[N];
int fin(int i){
if(p[i]==i) return i;
return p[i]=fin(p[i]);
}
void add(int a, int b){
while(a<N) fw[a] += b, a+=(a&-a);
}
int get(int a){
int b = 0;
while(a) b += fw[a], a-=(a&-a);
return b;
}
int bullshit(int a){ // binary search
int b = 0, c = 0;
for(int i=(1<<16); i>0; i>>=1){
int t = b + fw[c|i];
if(t <= a) b = t, c |= i;
//printf("zzzz%d %d\n",a,c);
}
return c;
}
int bs(int a){
int l=0, r=N-1;
while(l<r){
int m = (l+r)>>1;
if(get(m)<a) l = m+1;
else r = m;
}
return l;
}
void build(int l = 1, int r = n-1, int now = 1){
if(l == r){ seg[now] = num[l-1]; return ;}
int m = (l+r)>>1;
build(l, m, now<<1); build(m+1, r, now<<1|1);
seg[now] = max(seg[now<<1], seg[now<<1|1]);
}
int qu(int ll, int rr, int l = 1, int r = n-1, int now = 1){
if(l > rr || r < ll) return -1;
if(l >= ll && r <= rr) return seg[now];
int m = (l+r)>>1;
return max(qu(ll, rr, l, m, now<<1), qu(ll, rr, m+1, r, now<<1|1));
}
void dfs(int u, int v){
int ch = (qu(L[u], R[u]-1)<Rank);
//printf("==%d (%d,%d) %d\n",u,L[u],R[u],ch);
dp[u] = dp[v]+ch;
for(int e : g[u]){
//printf("%d\n",e);
dfs(e, u);
}
}
int GetBestPosition(int n1, int c, int r, int *K, int *S, int *E) {
// c is number of commands
// r is rank of the late knight
// K = rank of the knight in each positions (0 to n-1)
// S and E are just 'l' and 'r'
num = K;
n = n1;
Rank = r;
int i,j,k,a,b,d;
for(i=1;i<=n+1;i++) add(i, 1), p[i] = i;
for(i=0;i<c;i++){
int l = bullshit(S[i]+1);
int r = bullshit(E[i]+1);
L[i] = bs(S[i])+1;
R[i] = r;
it = interval.lower_bound({{L[i],0},0});
while(it != interval.end() && it->x.x >= L[i] && it->x.y <= R[i]){
it2 = it;
it++;
g[i].pb(it2->y);
interval.erase(it2);
}
//printf("##%d\n==%d %d\n",i,L[i],R[i]);
interval.insert({{L[i], R[i]},i});
for(j = l; j < r; j++){
//printf("xx%d\n",j);
add(j, -1);
p[j] = fin(j+1);
// if(get(j)-get(j-1)) add(j,-1);
}
}
build();
dfs(c-1, c);
PII ans = (PII){-2, 0};
for(i=0;i<c;i++) if(g[i].empty()) ans = max((PII){dp[i], -L[i]+1}, ans);
return -ans.y;
}
/*
5 3 3
1 0 2 4
1 3
0 1
0 1
10 9 9
8 7 6 5 4 3 2 1 0
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
*/
Compilation message
tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:82:10: warning: unused variable 'k' [-Wunused-variable]
int i,j,k,a,b,d;
^
tournament.cpp:82:12: warning: unused variable 'a' [-Wunused-variable]
int i,j,k,a,b,d;
^
tournament.cpp:82:14: warning: unused variable 'b' [-Wunused-variable]
int i,j,k,a,b,d;
^
tournament.cpp:82:16: warning: unused variable 'd' [-Wunused-variable]
int i,j,k,a,b,d;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
2680 KB |
Output is correct |
| 2 |
Runtime error |
14 ms |
6776 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16 ms |
6896 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
34 ms |
8296 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
