結果
問題 | No.945 YKC饅頭 |
ユーザー |
|
提出日時 | 2019-12-09 07:24:27 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 289 ms / 2,000 ms |
コード長 | 1,680 bytes |
コンパイル時間 | 568 ms |
コンパイル使用メモリ | 58,496 KB |
実行使用メモリ | 21,124 KB |
最終ジャッジ日時 | 2024-06-11 18:30:45 |
合計ジャッジ時間 | 9,592 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 74 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:77:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 77 | scanf("%d%d", &n, &m); | ~~~~~^~~~~~~~~~~~~~~~
ソースコード
#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]); }