| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 474232 |
2021-09-17T12:23:13 Z |
teee |
Treasure Hunt (CEOI11_tre) |
C++17 |
|
4000 ms |
187212 KB |
#include <iostream>
#include <vector>
#include <map>
#define ll long long
using namespace std;
struct node;
map<int,node*> mp;
struct node{
node *l,*r,*p;
int Mcnt,Scnt,key;
int lef;
bool rev;
node(int a,int b){
l=r=p= nullptr;
Mcnt=Scnt=b;
key=a;
rev=false;
lef=key;
}
};
bool isRoot(node * x) {
return (!x->p || (x->p->l != x && x->p->r != x));
}
void lazy_up(node* x){
if(!x)return;
if(x->rev){
if(x->l)x->l->rev^=1,swap(x->l->l,x->l->r);
if(x->r)x->r->rev^=1,swap(x->r->l,x->r->r);
x->rev=false;
}
}
void update(node* x){
lazy_up(x);
lazy_up(x->l);
lazy_up(x->r);
x->Scnt=x->Mcnt;
x->lef=x->key;
if(x->l){
x->Scnt+=x->l->Scnt;
x->lef=x->l->lef;
}
if(x->r)x->Scnt+=x->r->Scnt;
}
void rotate(node* x){
node* p=x->p;
lazy_up(p);lazy_up(x);
update(x);update(p);
if(x==p->l){
p->l=x->r;
if(p->l)p->l->p=p;
x->r=p;
}else{
p->r=x->l;
if(p->r)p->r->p=p;
x->l=p;
}
x->p=p->p;
p->p=x;
lazy_up(p);lazy_up(x);
update(x);update(p);
if(x->p){
if(p==x->p->l)x->p->l=x;
else if(p==x->p->r)x->p->r=x;
}
lazy_up(p);lazy_up(x);
update(x);update(p);
}
void splay(node* x){///thinking
while(!isRoot(x)){
node* p=x->p;
if (!isRoot(p)) lazy_up(p->p);
lazy_up(p);
lazy_up(x);
update(x);update(p);
if(!isRoot(p)){
if((x==p->l)^(p==p->p->l))rotate(x);
else rotate(p);
}
rotate(x);
}
lazy_up(x);update(x);
}
node* access(node* x){//////////thinking
lazy_up(x);update(x);
splay(x);
lazy_up(x);update(x);
x->r= nullptr;
node* res=x;
while(x->p){
node* p=x->p;
res=p;
splay(p);
p->r=x;
splay(x);
}
lazy_up(x);update(x);
return res;
}
void makeRoot(node * x) {
access(x);
swap(x->l,x->r);
x->rev = true;
lazy_up(x);
}
int now;
void init(){
mp[1]=new node(1,1);
now=2;
}
node* split(node* p,int a){/////////누구한테 자식을 뭘 줄지 오더는 어캐 할지
if(p->Mcnt==1)return p;
if(p->key==a){
node* pp=new node(a,1);
mp[a]=pp;
p->key++;p->Mcnt--;
mp[a+1]=p;
p->p=pp;pp->r=p;
p->l=pp->l;
if(pp->l)pp->l->p=p;
pp->l=nullptr;
update(pp);
update(p);p=pp;
}else{/////////////////
int k=a-p->key;///l
int nk=p->Mcnt-k-1;////r
if(nk){
node* pp=new node(a,1);
mp[a]=pp;
node*lp=new node(p->key,k);
mp[p->key]=lp;
p->Mcnt=nk;p->key=a+1;
mp[a+1]=p;
pp->r=p;p->p=pp;
lp->r=pp;pp->p=lp;
lp->l=p->l;
if(p->l)p->l->p=lp;
p->l=nullptr;
update(p);
update(pp);
update(lp);p=pp;
}else{
node*lp=new node(p->key,k);
mp[p->key]=lp;
p->key=a;p->Mcnt=1;
mp[a]=p;
lp->r=p;
p->p=lp;
lp->l=p->l;
if(p->l)p->l->p=lp;
p->l=nullptr;
update(p);
update(lp);
}
}
return p;
}
void path(int a, int s){
node* p=prev(mp.upper_bound(a))->second;
access(p);
p=split(p,a);
node* q=new node(now,s);
mp[now]=q;
q->p=p;p->r=q;
access(q);
now+=s;
}
int dig2(int a, int b){
node* p=prev(mp.upper_bound(a))->second;
node* pp=prev(mp.upper_bound(b))->second;
access(p);p=split(p,a);
access(pp);pp=split(pp,b);
makeRoot(p);
access(pp);
splay(p);
int cnt=(p->Scnt+1)/2;///몇칸 갈거임?
while(1){
update(p);
while(p->l&&p->l->Scnt >= cnt){
p=p->l;update(p);
}
if(p->l)cnt-=p->l->Scnt;
if(p->Mcnt >= cnt){
if(cnt==1)return p->key;
if(p->lef < p->key){
return p->key+cnt-1;
}return p->key+p->Mcnt-1-cnt+1;
}cnt-=p->Mcnt;
p=p->r;
}
}int dig(int a, int b){
int ans=dig2(a,b);
node*p=mp[1];
access(p);
makeRoot(p);
cout<<ans<<'\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
460 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
1016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1766 ms |
61444 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2172 ms |
66400 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2169 ms |
40308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2719 ms |
155124 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2285 ms |
102612 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4056 ms |
174376 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3285 ms |
187212 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3179 ms |
187068 KB |
Output isn't correct |
