Submission #860471

#	Time	Username	Problem	Language	Result	Execution time	Memory
860471		ReLice	Valley (BOI19_valley)	C++14	0 / 100	60 ms	1876 KiB

valley

#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 (stderr)

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);}
      |                                                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 27
• Subtask 3: 0 / 23
• Subtask 4: 0 / 41