//#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 a;
}
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;
}
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 ch = (qu(L[u], R[u]-1)<Rank);
//printf("==%d (%d,%d) %d\n",u,L[u],R[u],ch);
dp[u] = -1;
for(int e : g[u]){
//printf("%d\n",e);
dfs(e);
dp[u] = max(dp[u], dp[e]);
}
if(g[u].empty()) dp[u] = (ch)?1:-1;
else if(dp[u]!=-1) dp[u] = (ch)?dp[u]+1:-1;
}
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;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] = l;
R[i] = r;
it = interval.lower_bound({{l,0},0});
while(it != interval.end() && (it->x.y >= l || it->x.x <= r)){
it2 = it;
it++;
g[i].pb(it2->y);
L[i] = min(L[i], it2->x.y);
R[i] = max(R[i], it2->x.x);
interval.erase(it2);
}
//printf("##%d\n%d %d\n%d %d\n",i,l,r,L[i],R[i]);
interval.insert({{R[i], L[i]},i});
for(j = fin(l); j < r; j=fin(j+1)){
//printf("xx%d\n",j);
add(j, -1);
p[j] = fin(j+1);
}
}
build();
dfs(c-1);
PII ans = (PII){-2, 0};
for(i=0;i<c;i++) ans = max((PII){dp[i], -i}, ans);
return -ans.y;
}
/*
5 3 3
1 0 2 4
1 3
0 1
0 1
*/
Compilation message
tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:76:10: warning: unused variable 'k' [-Wunused-variable]
int i,j,k,a,b,d;
^
tournament.cpp:76:12: warning: unused variable 'a' [-Wunused-variable]
int i,j,k,a,b,d;
^
tournament.cpp:76:14: warning: unused variable 'b' [-Wunused-variable]
int i,j,k,a,b,d;
^
tournament.cpp:76:16: warning: unused variable 'd' [-Wunused-variable]
int i,j,k,a,b,d;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
2808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
2936 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
5856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
