結果

問題 No.618 labo-index
ユーザー tailstails
提出日時 2017-12-18 02:16:27
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 527 ms / 6,000 ms
コード長 1,097 bytes
コンパイル時間 1,359 ms
コンパイル使用メモリ 144,016 KB
実行使用メモリ 52,348 KB
最終ジャッジ日時 2023-08-22 05:19:54
合計ジャッジ時間 10,078 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 4 ms
4,376 KB
testcase_05 AC 5 ms
4,380 KB
testcase_06 AC 1 ms
4,376 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 3 ms
4,380 KB
testcase_09 AC 4 ms
4,376 KB
testcase_10 AC 4 ms
4,376 KB
testcase_11 AC 3 ms
4,384 KB
testcase_12 AC 4 ms
4,380 KB
testcase_13 AC 4 ms
4,380 KB
testcase_14 AC 4 ms
4,380 KB
testcase_15 AC 4 ms
4,380 KB
testcase_16 AC 5 ms
4,380 KB
testcase_17 AC 3 ms
4,376 KB
testcase_18 AC 7 ms
4,376 KB
testcase_19 AC 293 ms
27,936 KB
testcase_20 AC 323 ms
27,796 KB
testcase_21 AC 303 ms
27,536 KB
testcase_22 AC 309 ms
27,104 KB
testcase_23 AC 308 ms
27,552 KB
testcase_24 AC 303 ms
27,588 KB
testcase_25 AC 325 ms
27,624 KB
testcase_26 AC 315 ms
27,400 KB
testcase_27 AC 308 ms
26,432 KB
testcase_28 AC 285 ms
27,948 KB
testcase_29 AC 311 ms
27,720 KB
testcase_30 AC 297 ms
27,264 KB
testcase_31 AC 316 ms
26,844 KB
testcase_32 AC 312 ms
28,136 KB
testcase_33 AC 303 ms
27,872 KB
testcase_34 AC 505 ms
52,348 KB
testcase_35 AC 527 ms
10,392 KB
testcase_36 AC 339 ms
4,376 KB
testcase_37 AC 469 ms
27,792 KB
testcase_38 AC 1 ms
4,376 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:49:6: warning: ISO C++ forbids declaration of ‘main’ with no type [-Wreturn-type]
 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