結果

問題 No.618 labo-index
ユーザー tailstails
提出日時 2017-12-18 02:16:27
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 605 ms / 6,000 ms
コード長 1,097 bytes
コンパイル時間 1,249 ms
コンパイル使用メモリ 160,188 KB
実行使用メモリ 52,224 KB
最終ジャッジ日時 2024-05-09 11:14:58
合計ジャッジ時間 9,847 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 5 ms
5,376 KB
testcase_05 AC 6 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 3 ms
5,376 KB
testcase_08 AC 3 ms
5,376 KB
testcase_09 AC 4 ms
5,376 KB
testcase_10 AC 5 ms
5,376 KB
testcase_11 AC 3 ms
5,376 KB
testcase_12 AC 3 ms
5,376 KB
testcase_13 AC 5 ms
5,376 KB
testcase_14 AC 4 ms
5,376 KB
testcase_15 AC 5 ms
5,376 KB
testcase_16 AC 5 ms
5,376 KB
testcase_17 AC 3 ms
5,376 KB
testcase_18 AC 8 ms
5,376 KB
testcase_19 AC 299 ms
27,904 KB
testcase_20 AC 329 ms
27,648 KB
testcase_21 AC 316 ms
27,392 KB
testcase_22 AC 315 ms
27,008 KB
testcase_23 AC 325 ms
27,520 KB
testcase_24 AC 323 ms
27,648 KB
testcase_25 AC 331 ms
27,520 KB
testcase_26 AC 323 ms
27,264 KB
testcase_27 AC 319 ms
26,496 KB
testcase_28 AC 299 ms
27,904 KB
testcase_29 AC 315 ms
27,648 KB
testcase_30 AC 308 ms
27,392 KB
testcase_31 AC 326 ms
27,008 KB
testcase_32 AC 322 ms
27,904 KB
testcase_33 AC 309 ms
27,904 KB
testcase_34 AC 565 ms
52,224 KB
testcase_35 AC 605 ms
10,496 KB
testcase_36 AC 369 ms
5,376 KB
testcase_37 AC 528 ms
27,904 KB
testcase_38 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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