結果

問題 No.618 labo-index
ユーザー Sebastian KingSebastian King
提出日時 2017-12-18 16:32:02
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 240 ms / 6,000 ms
コード長 1,364 bytes
コンパイル時間 1,627 ms
コンパイル使用メモリ 168,160 KB
実行使用メモリ 16,768 KB
最終ジャッジ日時 2024-05-09 11:23:58
合計ジャッジ時間 5,743 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 3 ms
5,376 KB
testcase_05 AC 3 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 3 ms
5,376 KB
testcase_10 AC 3 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
testcase_15 AC 3 ms
5,376 KB
testcase_16 AC 3 ms
5,376 KB
testcase_17 AC 2 ms
5,376 KB
testcase_18 AC 3 ms
5,376 KB
testcase_19 AC 87 ms
8,832 KB
testcase_20 AC 99 ms
8,960 KB
testcase_21 AC 96 ms
8,960 KB
testcase_22 AC 101 ms
8,960 KB
testcase_23 AC 95 ms
8,960 KB
testcase_24 AC 92 ms
8,960 KB
testcase_25 AC 96 ms
8,704 KB
testcase_26 AC 99 ms
8,832 KB
testcase_27 AC 107 ms
8,960 KB
testcase_28 AC 85 ms
8,960 KB
testcase_29 AC 95 ms
8,960 KB
testcase_30 AC 100 ms
8,704 KB
testcase_31 AC 104 ms
8,832 KB
testcase_32 AC 98 ms
8,704 KB
testcase_33 AC 91 ms
8,960 KB
testcase_34 AC 237 ms
16,768 KB
testcase_35 AC 240 ms
16,768 KB
testcase_36 AC 37 ms
5,376 KB
testcase_37 AC 156 ms
10,624 KB
testcase_38 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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 # 

#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