#include <bits/stdc++.h>
#define ll long long
#define str string
#define ins insert
#define ld long double
#define pb push_back
#define pf push_front
#define pof pop_front()
#define pob pop_back()
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define fr first
#define sc second
#define sz size()
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define bc back()
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
void start(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
const ll inf=1e18+7;
const ll mod=998244353;
const ll N=130*2;;
const ld eps=1e-9;
struct node{
ll a,h,h2,hh;
node* l;
node* r;
};
node* newp(ll a){
node* b=new node();
b->a=a;
b->h=b->h2=0ll;
b->hh=1ll;
b->l=b->r=NULL;
return b;
}
node* next(node* v,ll a){
if(v==NULL) return v;
if(a>=v->a){
return next(v->r,a);
}else{
node* x=next(v->l,a);
if(x==NULL || x->a<=a) return v;
return x;
}
}
node* prev(node* v,ll a){
if(v==NULL) return NULL;
if(a>v->a){
node* x=prev(v->r,a);
if(x==NULL || x->a>=a) return v;
return x;
}else{
return prev(v->l,a);
}
}
bool check(node* v,ll a){
if(v==NULL) return false;
if(v->a==a) return true;
if(a>v->a) return check(v->r,a);
else return check(v->l,a);
}
node* rotl(node* v){
node* x=v;
node* y=v->r;
x->r=y->l;
if(x->r!=NULL)x->h2=x->r->hh;
else x->h2=0ll;
x->hh=max(x->h,x->h2)+1ll;
y->l=x;
y->h=y->l->hh;
y->hh=max(y->h,y->h2)+1ll;
return y;
}
node* rotr(node* v){
node* x=v;
node* y=v->l;
x->l=y->r;
if(x->l!=NULL)x->h=x->l->hh;
else x->h=0ll;
x->hh=max(x->h,x->h2)+1ll;
y->r=x;
y->h2=y->r->hh;
y->hh=max(y->h,y->h2)+1ll;
return y;
}
node* bal(node* v){
if(abs(v->h-v->h2)<2)return v;
if(v->h2>v->h){
if(v->r->h2>v->r->h){
v=rotl(v);
}
else{
v->r=rotr(v->r);
v=rotl(v);
}
}
else{
if(v->l->h>v->l->h2){
v=rotr(v);
}
else{
v->l=rotl(v->l);
v=rotr(v);
}
}
return v;
}
node* ins(node* v,ll a){
if(v==NULL){
return newp(a);
}
if(a==v->a) return v;
else if(a>v->a){
v->r=ins(v->r,a);
if(v->r!=NULL)v->h2=v->r->hh;
}else{
v->l=ins(v->l,a);
if(v->l!=NULL)v->h=v->l->hh;
}
v->hh=max(v->h,v->h2)+1ll;
v=bal(v);
return v;
}
node* mx(node* v){
if(v->r==NULL){
return v;
}else {
node* b=mx(v->r);
if(b==v->r) {v->r=b->l;b->l=NULL;}
if(v->r!=NULL) v->h2=v->r->hh;
else v->h2=0;
v->hh=max(v->h,v->h2)+1ll;
v=bal(v);
return b;
}
}
node* del(node* v,ll a){
if(v==NULL){
return v;
}
if(a==v->a) {
if(v->l==NULL && v->r==NULL)return NULL;
if(v->l==NULL) return v->r;
if(v->r==NULL) return v->l;
node* b=mx(v->l);
if(v->l!=b && b!=NULL){
b->l=v->l;
v->h=v->l->hh;
}
else {
b->l=NULL;
v->h=0ll;
}
v->hh=max(v->h,v->h2)+1ll;
b->r=v->r;
b->hh=v->hh;
b->h2=v->h2;
b->h=v->h;
if(b!=NULL)b=bal(b);
return b;
}
else if(a>v->a){
v->r=del(v->r,a);
if(v->r!=NULL)v->h2=v->r->hh;
}else{
v->l=del(v->l,a);
if(v->l!=NULL)v->h=v->l->hh;
}
v->hh=max(v->h,v->h2)+1ll;
v=bal(v);
return v;
}
void go(node* v){
if(v==NULL)return ;
cout<<v->a<<' ';
go(v->l);
go(v->r);
}
void solve(){
ll b;
node* r=NULL;
str s;
while(cin>>s){
cin>>b;
if(s=="insert"){
r=ins(r,b);
}else if(s=="delete"){
r=del(r,b);
}else if(s=="exists"){
if(check(r,b))cout<<"true"<<endl;
else cout<<"false"<<endl;
}else if(s=="next"){
if(next(r,b)==NULL)cout<<"none"<<endl;
else cout<<next(r,b)->a<<endl;
}else{
if(prev(r,b)==NULL)cout<<"none"<<endl;
else cout<<prev(r,b)->a<<endl;
}
}
}
signed main(){
start();
ll t=1;
//cin>>t;
while(t--) solve();
}
/*
insert 1
insert 2
insert 3
insert 4
insert 5
insert 6
insert 7
insert 8
*/
Compilation message
valley.cpp: In function 'void fre(std::string)':
valley.cpp:24:27: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
24 | void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:24:64: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
24 | void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
60 ms |
1876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
