結果
問題 | No.945 YKC饅頭 |
ユーザー |
|
提出日時 | 2019-12-08 05:25:13 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 419 ms / 2,000 ms |
コード長 | 1,724 bytes |
コンパイル時間 | 1,854 ms |
コンパイル使用メモリ | 167,384 KB |
実行使用メモリ | 10,624 KB |
最終ジャッジ日時 | 2024-12-27 16:03:08 |
合計ジャッジ時間 | 12,976 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 74 |
ソースコード
#include "bits/stdc++.h" using namespace std; typedef long long ll; typedef pair<int, char> P; const int INF = (1<<30); const ll INFLL = (1ll<<60); const ll MOD = (ll)(1e9+7); #define l_ength size void mul_mod(ll& a, ll b){ a *= b; a %= MOD; } void add_mod(ll& a, ll b){ a = (a<MOD)?a:(a-MOD); b = (b<MOD)?b:(b-MOD); a += b; a = (a<MOD)?a:(a-MOD); } int n,m,segtree[816225][2]; bool delayed[816225]; char t[816225]; void eval(int i, int l, int r){ if(delayed[i]){ segtree[i][0] = min(segtree[i][0],segtree[i][1]); if(r-l>1){ delayed[2*i+1] = true; delayed[2*i+2] = true; segtree[2*i+1][1] = min(segtree[2*i+1][1],segtree[i][1]); segtree[2*i+2][1] = min(segtree[2*i+2][1],segtree[i][1]); } delayed[i] = false; } } void update(int a, int b, int v, int i=0, int l=0, int r=n){ eval(i,l,r); if(b<=l || r<=a){ return; } if(a<=l && r<=b){ segtree[i][1] = min(segtree[i][1],v); delayed[i] = true; eval(i,l,r); }else{ update(a,b,v,2*i+1,l,(l+r)/2); update(a,b,v,2*i+2,(l+r)/2,r); segtree[i][0] = min(segtree[2*i+1][0],segtree[2*i+2][0]); } } int query(int a, int b, int i=0, int l=0, int r=n){ int vl,vr; eval(i,l,r); if(b<=l || r<=a){ return m; } if(a<=l && r<=b){ return segtree[i][0]; }else{ vl = query(a,b,2*i+1,l,(l+r)/2); vr = query(a,b,2*i+2,(l+r)/2,r); return min(vl,vr); } } int main(void){ int i,l,r,y=0,k=0,c=0; cin >> n >> m; fill(segtree[0],segtree[816225],m); for(i=0; i<m; ++i){ cin >> l >> r >> t[i]; update(l-1,r,i); } t[m] = '@'; for(i=0; i<n; ++i){ switch(t[query(i,i+1)]){ case 'Y': ++y; break; case 'K': ++k; break; case 'C': ++c; break; } } cout << y << " " << k << " " << c << endl; return 0; }