結果

問題 No.945 YKC饅頭
ユーザー ianCKianCK
提出日時 2019-12-09 07:24:27
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 366 ms / 2,000 ms
コード長 1,680 bytes
コンパイル時間 734 ms
コンパイル使用メモリ 62,612 KB
実行使用メモリ 20,452 KB
最終ジャッジ日時 2023-09-02 11:48:08
合計ジャッジ時間 13,531 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
13,788 KB
testcase_01 AC 4 ms
13,996 KB
testcase_02 AC 4 ms
13,732 KB
testcase_03 AC 4 ms
13,824 KB
testcase_04 AC 4 ms
13,720 KB
testcase_05 AC 4 ms
13,740 KB
testcase_06 AC 4 ms
13,808 KB
testcase_07 AC 4 ms
13,748 KB
testcase_08 AC 4 ms
13,724 KB
testcase_09 AC 4 ms
13,748 KB
testcase_10 AC 4 ms
13,724 KB
testcase_11 AC 4 ms
13,732 KB
testcase_12 AC 4 ms
13,736 KB
testcase_13 AC 5 ms
13,816 KB
testcase_14 AC 5 ms
13,740 KB
testcase_15 AC 4 ms
13,884 KB
testcase_16 AC 3 ms
13,788 KB
testcase_17 AC 4 ms
13,844 KB
testcase_18 AC 5 ms
13,996 KB
testcase_19 AC 4 ms
14,004 KB
testcase_20 AC 3 ms
13,740 KB
testcase_21 AC 4 ms
13,800 KB
testcase_22 AC 4 ms
13,852 KB
testcase_23 AC 5 ms
13,760 KB
testcase_24 AC 5 ms
13,856 KB
testcase_25 AC 5 ms
13,748 KB
testcase_26 AC 5 ms
13,888 KB
testcase_27 AC 4 ms
13,788 KB
testcase_28 AC 3 ms
13,752 KB
testcase_29 AC 4 ms
13,728 KB
testcase_30 AC 4 ms
13,728 KB
testcase_31 AC 14 ms
13,836 KB
testcase_32 AC 8 ms
17,856 KB
testcase_33 AC 62 ms
18,852 KB
testcase_34 AC 155 ms
19,096 KB
testcase_35 AC 257 ms
20,304 KB
testcase_36 AC 174 ms
15,628 KB
testcase_37 AC 163 ms
15,480 KB
testcase_38 AC 153 ms
15,188 KB
testcase_39 AC 35 ms
18,352 KB
testcase_40 AC 32 ms
18,548 KB
testcase_41 AC 13 ms
17,880 KB
testcase_42 AC 220 ms
19,732 KB
testcase_43 AC 149 ms
15,472 KB
testcase_44 AC 191 ms
19,928 KB
testcase_45 AC 238 ms
19,856 KB
testcase_46 AC 8 ms
17,900 KB
testcase_47 AC 143 ms
19,072 KB
testcase_48 AC 32 ms
14,032 KB
testcase_49 AC 62 ms
18,296 KB
testcase_50 AC 259 ms
19,916 KB
testcase_51 AC 360 ms
20,380 KB
testcase_52 AC 326 ms
20,452 KB
testcase_53 AC 325 ms
20,400 KB
testcase_54 AC 366 ms
20,440 KB
testcase_55 AC 329 ms
20,440 KB
testcase_56 AC 8 ms
18,376 KB
testcase_57 AC 8 ms
18,352 KB
testcase_58 AC 153 ms
20,056 KB
testcase_59 AC 193 ms
20,344 KB
testcase_60 AC 69 ms
19,016 KB
testcase_61 AC 165 ms
20,024 KB
testcase_62 AC 161 ms
19,948 KB
testcase_63 AC 10 ms
18,372 KB
testcase_64 AC 77 ms
19,344 KB
testcase_65 AC 61 ms
19,188 KB
testcase_66 AC 59 ms
18,892 KB
testcase_67 AC 117 ms
19,564 KB
testcase_68 AC 71 ms
19,104 KB
testcase_69 AC 27 ms
18,552 KB
testcase_70 AC 32 ms
18,616 KB
testcase_71 AC 34 ms
18,612 KB
testcase_72 AC 96 ms
19,244 KB
testcase_73 AC 178 ms
20,160 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
using namespace std;
constexpr int kM = int(2E5 + 10);

struct Query {
	int l, r, c;
	void in() {
		string s;
		cin >> l >> r >> s;
		if (s[0] == 'Y') c = 1;
		else if (s[0] == 'K') c = 2;
		else c = 3;
		return ;
	}
};

struct seg_tree {
	int y[kM << 2], k[kM << 2], c[kM << 2], flag[kM << 2], sz[kM << 2];
	void pull(int n) {
		y[n] = y[n * 2 + 1] + y[n * 2 + 2];
		k[n] = k[n * 2 + 1] + k[n * 2 + 2];
		c[n] = c[n * 2 + 1] + c[n * 2 + 2];
		return ;
	}
	void addtag(int n, int x) {
		if (x == 1) {
			k[n] = c[n] = 0;
			y[n] = sz[n];
		}
		else if (x == 2) {
			y[n] = c[n] = 0;
			k[n] = sz[n];
		}
		else {
			y[n] = k[n] = 0;
			c[n] = sz[n];
		}
		flag[n] = x;
		return ;
	}
	void push(int n) {
		if (flag[n]) {
			addtag(n * 2 + 1, flag[n]);
			addtag(n * 2 + 2, flag[n]);
			flag[n] = 0;
		}
		return ;
	}
	void init(int n, int l, int r) {
		sz[n] = r - l + 1;
		y[n] = k[n] = c[n] = flag[n] = 0;
		if (l < r) {
			int mid = (l + r) >> 1;
			init(n * 2 + 1, l, mid);
			init(n * 2 + 2, mid + 1, r);
		}
		return ;
	}
	void fix(int n, int l, int r, int L, int R, int x) {
		if (L <= l && r <= R) addtag(n, x);
		else if (!(l > R || L > r)) {
			int mid = (l + r) >> 1;
			push(n);
			fix(n * 2 + 1, l, mid, L, R, x);
			fix(n * 2 + 2, mid + 1, r, L, R, x);
			pull(n);
		}
		return ;
	}
};

seg_tree sg;
Query query[kM];

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++) query[i].in();
	sg.init(0, 1, n);
	for (int i = m; i >= 1; i--) sg.fix(0, 1, n, query[i].l, query[i].r, query[i].c);
	printf("%d %d %d\n", sg.y[0], sg.k[0], sg.c[0]);
}
0