#include<stdio.h>
#include<algorithm>
#define Ptreap pair<treap *, treap *>
using namespace std;
int Res, RR, Ans;
struct treap{
int key, pri, sz, d, g1, g2;
treap *c1, *c2;
treap(int key_, int d_, int g1_, int g2_){
key = key_, sz = 1, d = d_, g1 = g1_, g2 = g2_;
if(g1 <= RR){
if(Res < d)Ans = key, Res = d;
}
c1 = c2 = NULL;
pri = rand();
}
void setLeft(treap *nd){
c1 = nd;
CalcSize();
}
void setRight(treap *nd){
c2 = nd;
CalcSize();
}
void CalcSize(){
sz = 1;
if(c1) sz += c1->sz;
if(c2) sz += c2->sz;
}
};
Ptreap Divide(treap *root, int key){
if(root == NULL)return Ptreap(NULL, NULL);
if(root->key < key){
Ptreap tp = Divide(root->c2, key);
root->setRight(tp.first);
return Ptreap(root, tp.second);
}
Ptreap tp = Divide(root->c1, key);
root->setLeft(tp.second);
return Ptreap(tp.first, root);
}
treap *Ins(treap *root, treap *nd){
if(root == NULL)return nd;
if(root->pri < nd->pri){
Ptreap tp = Divide(root, nd->key);
nd->setLeft(tp.first);
nd->setRight(tp.second);
return nd;
}
if(root->key < nd->key){
root->setRight(Ins(root->c2, nd));
}
else{
root->setLeft(Ins(root->c1, nd));
}
return root;
}
treap *Merge(treap *c1, treap *c2){
if(c1 == NULL)return c2;
if(c2 == NULL)return c1;
if(c1->pri < c2->pri){
c2->setLeft(Merge(c1, c2->c1));
return c2;
}
c1->setRight(Merge(c1->c2, c2));
return c1;
}
treap *Del(treap *root, int key){
if(root->key == key)return Merge(root->c1, root->c2);
if(root->key < key){
root->setRight(Del(root->c2, key));
}
else{
root->setLeft(Del(root->c1, key));
}
return root;
}
treap *OSRank(treap *root, int cnt){
if(root->c1 && root->c1->sz >= cnt)return OSRank(root->c1, cnt);
if(root->c1)cnt -= root->c1->sz;
if(cnt==1)return root;
return OSRank(root->c2,cnt-1);
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
int i, j, d, g1, g2, key;
treap *Root = NULL, *tp;
Res = -1, RR = R;
for(i=0;i<N - 1;i++){
Root = Ins(Root, new treap(i, 0, -1, K[i]));
}
Root = Ins(Root, new treap(i, 0, -1, -1));
for(i=0;i<C;i++){
d=0,g1=g2=-1;
for(j=0;j<=E[i]-S[i];j++){
tp = OSRank(Root, S[i]+1);
if(d < tp->d + 1){
key = tp->key;
d = tp->d + 1;
}
g1 = max(g1, tp->g1);
if(j != E[i]-S[i])g1 = max(g1, tp->g2);
else g2 = tp->g2;
Root = Del(Root, tp->key);
}
Ins(Root, new treap(key, d, g1, g2));
}
return Ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
1208 KB |
SIGSEGV Segmentation fault |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
1208 KB |
SIGSEGV Segmentation fault |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
72 ms |
5348 KB |
SIGSEGV Segmentation fault |
| 2 |
Halted |
0 ms |
0 KB |
- |
