結果

問題 No.618 labo-index
コンテスト
ユーザー Sebastian King
提出日時 2017-12-18 16:32:02
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 127 ms / 6,000 ms
コード長 1,364 bytes
コンパイル時間 1,468 ms
コンパイル使用メモリ 168,060 KB
実行使用メモリ 16,768 KB
最終ジャッジ日時 2024-12-15 23:52:16
合計ジャッジ時間 4,522 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 35
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:33:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   33 |         scanf("%d", &Q);
      |         ~~~~~^~~~~~~~~~
main.cpp:36:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   36 |                 scanf("%d%d", &ty[i], &tx[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

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