Submission #860463

#	Time	Username	Problem	Language	Result	Execution time	Memory
860463		ReLice	Valley (BOI19_valley)	C++14	0 / 100	61 ms	5552 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{
		if(v->l==NULL) return v;
		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){
		if(v->r==NULL) return v;
		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* bal(node* v){
	if(abs(v->h-v->h2)<2)return v;
	if(v->h2>v->h){
		node* b=v->r;
		if(b->h2>b->h){
			v->r=b->l;
			b->l=v;
			if(v->l!=NULL)v->h=v->l->hh;
			if(v->r!=NULL)v->h2=v->r->hh;
			v->hh=max(v->h,v->h2)+1;
			if(b->l!=NULL)b->h=b->l->hh;
			if(b->r!=NULL)b->h2=b->r->hh;
			b->hh=max(b->h,b->h2)+1;
			return b;
		}
		else{
			node* z=b->l;
			v->r=z->l;
			b->l=z->r;
			z->l=v;
			z->r=b;
			if(z->l!=NULL)z->h=z->l->hh;
			if(z->r!=NULL)z->h2=z->r->hh;
			z->hh=max(z->h,z->h2)+1;
			if(v->l!=NULL)v->h=v->l->hh;
			if(v->r!=NULL)v->h2=v->r->hh;
			v->hh=max(v->h,v->h2)+1;
			if(b->l!=NULL)b->h=b->l->hh;
			if(b->r!=NULL)b->h2=b->r->hh;
			b->hh=max(b->h,b->h2)+1;
			return z;
		}
		
	}else{
		node* b=v->l;
		if(b->h>b->h2){
			v->l=b->r;
			b->r=v;
			if(v->l!=NULL)v->h=v->l->hh;
			if(v->r!=NULL)v->h2=v->r->hh;
			v->hh=max(v->h,v->h2)+1;
			if(b->l!=NULL)b->h=b->l->hh;
			if(b->r!=NULL)b->h2=b->r->hh;
			b->hh=max(b->h,b->h2)+1;
			return b;
		}
		else{
			node* z=b->r;
			v->l=z->r;
			b->r=z->l;
			z->r=v;
			z->l=b;
			if(z->l!=NULL)z->h=z->l->hh;
			if(z->r!=NULL)z->h2=z->r->hh;
			z->hh=max(z->h,z->h2)+1;
			if(v->l!=NULL)v->h=v->l->hh;
			if(v->r!=NULL)v->h2=v->r->hh;
			v->hh=max(v->h,v->h2)+1;
			if(b->l!=NULL)b->h=b->l->hh;
			if(b->r!=NULL)b->h2=b->r->hh;
			b->hh=max(b->h,b->h2)+1;
			return z;
		}
	}
}
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;
		if(v->r!=NULL) v->h2=v->r->hh;
		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;
		if(b!=NULL)b->r=v->r;
		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)+1;
	v=bal(v);
	return v;
}
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();
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    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