結果

問題 No.618 labo-index
ユーザー tails
提出日時 2017-12-18 02:16:27
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 539 ms / 6,000 ms
コード長 1,097 bytes
コンパイル時間 1,464 ms
コンパイル使用メモリ 160,336 KB
実行使用メモリ 52,224 KB
最終ジャッジ日時 2024-12-15 23:38:36
合計ジャッジ時間 9,219 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 35
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:49:1: warning: ISO C++ forbids declaration of ‘main’ with no type [-Wreturn-type]
   49 | main(){
      | ^~~~

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct Node {
	int count;
	Node * p1;
	Node * p2;
	Node(){
		count=0;
		p1=0;
		p2=0;
	}
};

void add(Node*p,ll v,ll l,ll r,int inc){
	p->count+=inc;
	if(l<r-1){
		ll c=(l+r)/2;
		if(v<c){
			if(!p->p1){
				p->p1=new Node;
			}
			add(p->p1,v,l,c,inc);
		}else{
			if(!p->p2){
				p->p2=new Node;
			}
			add(p->p2,v,c,r,inc);
		}
	}
}

int count(Node*p,ll v,ll l,ll r){
	ll c=(l+r)/2;
	if(v<c){
		return (p->p1 ? count(p->p1,v,l,c) : 0) + (p->p2 ? p->p2->count : 0);
	}else{
		return (p->p2 ? count(p->p2,v,c,r) : 0);
	}
}

Node * root;

ll a[100010];
int n;

main(){
	root=new Node;

	ll offset=1ll<<49;
	int Q;
	cin>>Q;

	for(int i=0;i<Q;++i){
		int t,x;
		cin>>t>>x;
		if(t==1){
			ll y=x+offset;
			a[++n]=y;
			add(root,y,0,1ll<<50,1);
		}
		if(t==2){
			ll y=a[x];
			add(root,y,0,1ll<<50,-1);
		}
		if(t==3){
			offset-=x;
		}

		{
			int l=0;
			int r=root->count+1;
			while(l<r-1){
				int c=(l+r)/2;
				if(count(root,c+offset-1,0,1ll<<50)>=c){
					l=c;
				}else{
					r=c;
				}
			}
			cout<<l<<endl;
		}
	}
}
0