結果

問題 No.618 labo-index
コンテスト
ユーザー Sebastian King
提出日時 2017-12-18 16:32:02
言語 C++11
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=gnu++11 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 101 ms / 6,000 ms
コード長 1,364 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,026 ms
コンパイル使用メモリ 188,296 KB
実行使用メモリ 17,152 KB
最終ジャッジ日時 2026-05-26 06:14:49
合計ジャッジ時間 3,795 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>

using namespace std;

typedef __int128 ll;

const int MAXN = 5e5 + 10;

int Q, N, M, cnt;
ll now, f[MAXN], b[MAXN];
int tx[MAXN], ty[MAXN], a[MAXN];

void add(int x){ for (int i = M - 1 + x; i; i /= 2) a[i]++; }
void del(int x){ for (int i = M - 1 + x; i; i /= 2) a[i]--; }

int test(int L){
	int ret = 0, l = 1, r = M;
	if (b[1] + now >= L) return L <= a[1];
	for (int i = 1; l != r; ){
		int m = (l + r) / 2;
		if (b[m + 1] + now >= L){
			ret += a[i * 2 + 1];
			r = m, i = i * 2;
		}
		else{
			l = m + 1, i = i * 2 + 1;
		}
	}
	return ret >= L;
}

int main(){
	scanf("%d", &Q);
	map<ll, int> X;
	for (int i = 1; i <= Q; i++){
		scanf("%d%d", &ty[i], &tx[i]);
		if (ty[i] == 3)
			now += tx[i];
		if (ty[i] == 1){
			X[tx[i] - now] = 1;
			f[++cnt] = tx[i] - now;
		}
	}
	for (auto &x : X){
		x.second = ++N;
		b[N] = x.first;
	}
	for (M = 1; M < N; M *= 2);
	for (int i = N + 1; i <= M; i++)
		b[i] = b[N] + Q + 2;
	now = 0;
	int ans = 0;
	for (int i = 1; i <= Q; i++){
		if (ty[i] == 1){
			add(X[tx[i] - now]);
			ans += test(ans + 1);
		}
		else if (ty[i] == 2){
			del(X[f[tx[i]]]);
			ans -= (!test(ans));
		}
		else {
			now += tx[i];
			int L = 0, R = a[1] + 1;
			while (L + 1 < R){
				int Mid = (L + R) / 2;
				if (test(Mid))
					L = Mid;
				else
					R = Mid;
			}
			ans =L;
		}
		printf("%d\n", ans);
	}
	return 0;
}
0