結果
問題 | No.2338 Range AtCoder Query |
ユーザー | momoyuu |
提出日時 | 2023-06-03 00:17:27 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 858 ms / 4,000 ms |
コード長 | 3,269 bytes |
コンパイル時間 | 3,373 ms |
コンパイル使用メモリ | 258,400 KB |
実行使用メモリ | 22,956 KB |
最終ジャッジ日時 | 2024-06-09 02:40:21 |
合計ジャッジ時間 | 22,410 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 5 ms
11,956 KB |
testcase_01 | AC | 6 ms
11,960 KB |
testcase_02 | AC | 6 ms
12,080 KB |
testcase_03 | AC | 5 ms
11,952 KB |
testcase_04 | AC | 6 ms
12,072 KB |
testcase_05 | AC | 5 ms
11,956 KB |
testcase_06 | AC | 9 ms
11,988 KB |
testcase_07 | AC | 8 ms
12,104 KB |
testcase_08 | AC | 8 ms
11,972 KB |
testcase_09 | AC | 8 ms
12,104 KB |
testcase_10 | AC | 8 ms
12,112 KB |
testcase_11 | AC | 671 ms
17,844 KB |
testcase_12 | AC | 600 ms
18,000 KB |
testcase_13 | AC | 667 ms
17,960 KB |
testcase_14 | AC | 617 ms
17,832 KB |
testcase_15 | AC | 769 ms
18,320 KB |
testcase_16 | AC | 848 ms
20,508 KB |
testcase_17 | AC | 856 ms
20,488 KB |
testcase_18 | AC | 855 ms
20,608 KB |
testcase_19 | AC | 846 ms
20,596 KB |
testcase_20 | AC | 839 ms
20,652 KB |
testcase_21 | AC | 853 ms
20,512 KB |
testcase_22 | AC | 858 ms
20,628 KB |
testcase_23 | AC | 829 ms
20,588 KB |
testcase_24 | AC | 841 ms
20,556 KB |
testcase_25 | AC | 843 ms
20,532 KB |
testcase_26 | AC | 63 ms
17,796 KB |
testcase_27 | AC | 64 ms
18,260 KB |
testcase_28 | AC | 60 ms
17,616 KB |
testcase_29 | AC | 565 ms
20,692 KB |
testcase_30 | AC | 844 ms
20,632 KB |
testcase_31 | AC | 542 ms
22,956 KB |
testcase_32 | AC | 483 ms
21,292 KB |
testcase_33 | AC | 405 ms
20,656 KB |
testcase_34 | AC | 397 ms
20,552 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll = long long; const int mx = 2e5+10; int nnn[mx],now[mx],l[mx],r[mx],ccc[mx],cnc[mx],nxt[mx]; int p[mx]; int n,m,q; const int B = 600; char s[mx]; int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); cin>>n>>m>>q; for(int i = 0;i<n;i++){ cin>>p[i]; string a; cin>>a; if(a=="AC") s[i] = 1; } int mx = 2e5; vector<vector<int>> is(mx+1); for(int i = 0;i<n;i++){ is[p[i]].push_back(i); } for(int i = 0;i<=mx;i++){ int now = 0; int ni = -1; if(is[i].size()==0) continue; for(int j = is[i].size()-1;j>=0;j--){ if(s[is[i][j]]){ cnc[is[i][j]] = now; nxt[is[i][j]] = ni; now= 0; ni = is[i][j]; }else{ now++; } } } for(int i = 0;i<q;i++){ cin>>l[i]>>r[i]; l[i]--; } vector<int> idx(q); for(int i = 0;i<q;i++) idx[i] = i; sort(idx.begin(),idx.end(),[&](int i,int j){ if(l[i]/B!=l[j]/B) return l[i] < l[j]; if(l[i]/B%2) return r[i] > r[j]; return r[i] < r[j]; }); int ans = 0; int cnt = 0; int nl = 0; int nr = 1; vector<pair<int,int>> aa(q); if(s[0]){ ans++; nnn[p[0]]++; now[p[0]]++; }else{ now[p[0]]++; } for(int i = 0;i<q;i++){ int ni = idx[i]; while(l[ni]<nl){ nl--; if(s[nl]){ cnt -= ccc[p[nl]]; ccc[p[nl]]=0; nnn[p[nl]]++; if(nnn[p[nl]]==1) ans++; now[p[nl]]++; }else{ if(nnn[p[nl]]){ cnt++; ccc[p[nl]]++; } now[p[nl]]++; } } while(nr<r[ni]){ if(s[nr]){ if(nnn[p[nr]]==0){ ans++; ccc[p[nr]] += now[p[nr]]; cnt += ccc[p[nr]]; } nnn[p[nr]]++; now[p[nr]]++; nr++; }else{ now[p[nr]]++; nr++; } } while(nl<l[ni]){ if(s[nl]){ nnn[p[nl]]--; now[p[nl]]--; if(nnn[p[nl]]){ int ni = cnc[nl]; cnt += ccc[p[nl]] += ni; }else{ ans--; } nl++; }else{ now[p[nl]]--; if(nnn[p[nl]]){ ccc[p[nl]]--; cnt--; } nl++; } } while(nr>r[ni]){ nr--; if(s[nr]){ now[p[nr]]--; nnn[p[nr]]--; if(nnn[p[nr]]==0){ cnt -= ccc[p[nr]]; ccc[p[nr]] = 0; ans--; } }else{ now[p[nr]]--; } } aa[ni] = make_pair(ans,cnt); } for(int i = 0;i<q;i++) cout<<aa[i].first<<" "<<aa[i].second<<endl; }