#include<bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
#define eb emplace_back
using ll=long long;
#define f first
#define s second
mt19937 rng(time(nullptr));
struct info{
int vL,vR,mn,mx;
info():vL(1e9),vR(-1),mn(1e9),mx(-1){}
info(int vL,int vR):vL(vL),vR(vR),mn(vL),mx(vR){}
};
struct treap{
struct node{
int sz,prio;
info val;
node *l,*r;
node(info val):sz(1),val(val),prio(rng()),l(nullptr),r(nullptr){}
};
using pnode=node*;
pnode rt;
int sz(pnode t){return t?t->sz:0;}
info val(pnode t){return t?t->val:info();}
void upd(pnode t){
if(!t) return;
t->sz=sz(t->l)+1+sz(t->r);
t->val.mn=min(val(t->l).mn,t->val.vL);
t->val.mx=max(val(t->r).mx,t->val.vR);
}
void split(pnode t,pnode &l,pnode &r,int x){
if(!t) return void(l=r=nullptr);
if(sz(t->l)>=x) split(t->l,l,t->l,x),r=t;
else split(t->r,t->r,r,x-sz(t->l)-1),l=t;
upd(t);
}
void merge(pnode &t,pnode l,pnode r){
if(!l||!r) return void(t=l?l:r);
if(l->prio>r->prio) merge(l->r,l->r,r),t=l;
else merge(r->l,l,r->l),t=r;
upd(t);
}
void init(int n){
rt=nullptr;
for(int i=0;i<n;++i) merge(rt,rt,new node(info(i,i)));
}
pii qr(int l,int r){
pnode t1,t2,t3;
split(rt,t1,t2,l-1);
split(t2,t2,t3,r-l+1);
pii ret(val(t2).mn,val(t2).mx);
merge(rt,t1,new node(info(ret.f,ret.s)));
merge(rt,rt,t3);
return ret;
}
}t;
int lm[100005],rm[100005];
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
vector<pii> opr(C);
t.init(N);
for(int i=0;i<C;++i){
auto [l,r]=t.qr(S[i]+1,E[i]+1);
opr[i]={l,r};
// cerr<<l<<"-"<<r<<endl;
}
sort(opr.begin(),opr.end());
for(int i=0,cur=-1;i<N-1;++i){
if(K[i]>R) cur=i;
lm[i]=cur;
}
for(int i=N-2,cur=N+1;i>=0;--i){
if(K[i]>R) cur=i;
rm[i]=cur;
}
int ans=0,mx=0;
for(int i=0;i<N;++i){
int cnt=0;
for(auto &[l,r]:opr){
if(l>i||r<i||rm[l]<r) continue;
++cnt;
}
if(cnt>mx) mx=cnt,ans=i;
}
return ans;
}
Compilation message
tournament.cpp: In constructor 'treap::node::node(info)':
tournament.cpp:19:10: warning: 'treap::node::val' will be initialized after [-Wreorder]
19 | info val;
| ^~~
tournament.cpp:18:12: warning: 'int treap::node::prio' [-Wreorder]
18 | int sz,prio;
| ^~~~
tournament.cpp:21:5: warning: when initialized here [-Wreorder]
21 | node(info val):sz(1),val(val),prio(rng()),l(nullptr),r(nullptr){}
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
448 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
348 KB |
Output is correct |
2 |
Correct |
29 ms |
976 KB |
Output is correct |
3 |
Correct |
2 ms |
604 KB |
Output is correct |
4 |
Correct |
23 ms |
1096 KB |
Output is correct |
5 |
Correct |
20 ms |
1296 KB |
Output is correct |
6 |
Correct |
13 ms |
984 KB |
Output is correct |
7 |
Correct |
29 ms |
860 KB |
Output is correct |
8 |
Correct |
23 ms |
860 KB |
Output is correct |
9 |
Correct |
1 ms |
604 KB |
Output is correct |
10 |
Correct |
22 ms |
1116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1079 ms |
5860 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |