結果
問題 | No.2338 Range AtCoder Query |
ユーザー | woodywoody |
提出日時 | 2023-06-03 02:19:04 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 3,412 ms / 4,000 ms |
コード長 | 8,174 bytes |
コンパイル時間 | 6,193 ms |
コンパイル使用メモリ | 280,880 KB |
実行使用メモリ | 29,696 KB |
最終ジャッジ日時 | 2024-06-09 03:11:00 |
合計ジャッジ時間 | 49,562 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 1 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,944 KB |
testcase_04 | AC | 1 ms
6,940 KB |
testcase_05 | AC | 1 ms
6,940 KB |
testcase_06 | AC | 3 ms
6,940 KB |
testcase_07 | AC | 2 ms
6,944 KB |
testcase_08 | AC | 3 ms
6,940 KB |
testcase_09 | AC | 2 ms
6,944 KB |
testcase_10 | AC | 3 ms
6,940 KB |
testcase_11 | AC | 1,550 ms
20,440 KB |
testcase_12 | AC | 1,341 ms
21,252 KB |
testcase_13 | AC | 1,635 ms
20,924 KB |
testcase_14 | AC | 1,582 ms
20,920 KB |
testcase_15 | AC | 1,931 ms
22,412 KB |
testcase_16 | AC | 2,441 ms
29,636 KB |
testcase_17 | AC | 2,530 ms
29,240 KB |
testcase_18 | AC | 2,471 ms
29,440 KB |
testcase_19 | AC | 2,518 ms
29,492 KB |
testcase_20 | AC | 2,416 ms
29,468 KB |
testcase_21 | AC | 2,890 ms
29,592 KB |
testcase_22 | AC | 2,427 ms
29,584 KB |
testcase_23 | AC | 2,452 ms
29,452 KB |
testcase_24 | AC | 2,441 ms
29,572 KB |
testcase_25 | AC | 2,399 ms
29,488 KB |
testcase_26 | AC | 66 ms
24,500 KB |
testcase_27 | AC | 52 ms
24,576 KB |
testcase_28 | AC | 55 ms
24,520 KB |
testcase_29 | AC | 3,412 ms
29,696 KB |
testcase_30 | AC | 2,381 ms
29,332 KB |
testcase_31 | AC | 953 ms
29,412 KB |
testcase_32 | AC | 872 ms
29,572 KB |
testcase_33 | AC | 217 ms
28,528 KB |
testcase_34 | AC | 212 ms
29,272 KB |
ソースコード
#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")// #pragma GCC optimize("O3,unroll-loops")// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")#include<bits/stdc++.h>#include<atcoder/all>#define rep(i,b) for(int i=0;i<b;i++)#define rrep(i,b) for(int i=b-1;i>=0;i--)#define rep1(i,b) for(int i=1;i<b;i++)#define repx(i,x,b) for(int i=x;i<b;i++)#define rrepx(i,x,b) for(int i=b-1;i>=x;i--)#define fore(i,a) for(auto& i:a)#define rng(x) (x).begin(), (x).end()#define rrng(x) (x).rbegin(), (x).rend()#define sz(x) ((int)(x).size())#define pb push_back#define fi first#define se second#define pcnt __builtin_popcountllusing namespace std;using namespace atcoder;using ll = long long;using ld = long double;template<typename T> using mpq = priority_queue<T, vector<T>, greater<T>>;template<typename T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }template<typename T> bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }template<typename T> ll sumv(const vector<T>&a){ll res(0);for(auto&&x:a)res+=x;return res;}bool yn(bool a) { if(a) {cout << "Yes" << endl; return true;} else {cout << "No" << endl; return false;}}#define dame { cout << "No" << endl; return;}#define dame1 { cout << -1 << endl; return;}#define cout2(x,y) cout << x << " " << y << endl;#define coutp(p) printf("%d %d\n",p.fi,p.se);#define out cout << ans << endl;#define outd cout << fixed << setprecision(20) << ans << endl;#define outm cout << ans.val() << endl;#define outv fore(yans , ans) cout << yans << "\n";#define outdv fore(yans , ans) cout << yans.val() << "\n";#define coutv(v) {fore(vy , v) {cout << vy << " ";} cout << endl;}#define coutv2(v) fore(vy , v) cout << vy << "\n";#define coutvm(v) {fore(vy , v) {cout << vy.val() << " ";} cout << endl;}#define coutvm2(v) fore(vy , v) cout << vy.val() << "\n";using pll = pair<ll,ll>;using pil = pair<int,ll>;using pli = pair<ll,int>;using pii = pair<int,int>;using pdd = pair<ld,ld>;using vi = vector<int>;using vd = vector<ld>;using vl = vector<ll>;using vs = vector<string>;using vb = vector<bool>;using vpii = vector<pii>;using vpli = vector<pli>;using vpll = vector<pll>;using vpil = vector<pil>;using vvi = vector<vector<int>>;using vvl = vector<vector<ll>>;using vvs = vector<vector<string>>;using vvb = vector<vector<bool>>;using vvpii = vector<vector<pii>>;using vvpli = vector<vector<pli>>;using vvpll = vector<vpll>;using vvpil = vector<vpil>;using mint = modint998244353;//using mint = modint1000000007;//using mint = dynamic_modint<0>;using vm = vector<mint>;using vvm = vector<vector<mint>>;vector<int> dx={1,0,-1,0,1,1,-1,-1},dy={0,1,0,-1,1,-1,1,-1};ll gcd(ll a, ll b) { return a?gcd(b%a,a):b;}ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}#define yes {cout <<"Yes"<<endl;}#define yesr { cout <<"Yes"<<endl; return;}#define no {cout <<"No"<<endl;}#define nor { cout <<"No"<<endl; return;}const double eps = 1e-10;const ll LINF = 1001002003004005006ll;const int INF = 1001001001;#ifdef MY_LOCAL_DEBUG#define show(x) cerr<<#x<<" = "<<x<<endl#define showp(p) cerr<<#p<<" = "<<p.fi<<" : "<<p.se<<endl#define show2(x,y) cerr<<#x<<" = "<<x<<" : "<<#y<<" = "<<y<<endl#define show3(x,y,z) cerr<<#x<<" = "<<x<<" : "<<#y<<" = "<<y<<" : "<<#z<<" = "<<z<<endl#define show4(x,y,z,x2) cerr<<#x<<" = "<<x<<" : "<<#y<<" = "<<y<<" : "<<#z<<" = "<<z<<" : "<<#x2<<" = "<<x2<<endl#define test(x) cout << "test" << x << endl#define showv(v) {fore(vy , v) {cout << vy << " ";} cout << endl;}#define showv2(v) fore(vy , v) cout << vy << "\n";#define showvm(v) {fore(vy , v) {cout << vy.val() << " ";} cout << endl;}#define showvm2(v) fore(vy , v) cout << vy.val() << "\n";#else#define show(x)#define showp(p)#define show2(x,y)#define show3(x,y,z)#define show4(x,y,z,x2)#define test(x)#define showv(v)#define showv2(v)#define showvm(v)#define showvm2(v)#endif// #ifdef MY_LOCAL_DEBUG// class CTimer {// const std::chrono::time_point<std::chrono::system_clock> start;// std::int64_t limit_microsec = 0;// public:// CTimer();// void set(std::int64_t time_microsec);// bool elapsed() const;// ld GetClocksMagni() const;// std::int64_t getMicrosec() const;// };// #else// class CTimer {// static const std::uint64_t ClocksPerMicrosec;// const std::uint64_t start_clocks;// std::uint64_t limit_clocks;// std::uint64_t getClocks() const;// public:// CTimer();// void set(std::int64_t time_microsec);// bool elapsed() const;// ld GetClocksMagni() const;// std::int64_t getMicrosec() const;// };// #endif// #ifdef MY_LOCAL_DEBUG// using namespace std::chrono;// CTimer::CTimer()// : start(system_clock::now()) {// }// void CTimer::set(std::int64_t time_microsec) {// limit_microsec += time_microsec;// }// bool CTimer::elapsed() const {// return getMicrosec() >= limit_microsec;// }// std::int64_t CTimer::getMicrosec() const {// return duration_cast<microseconds>(system_clock::now() - start).count();// }// ld CTimer::GetClocksMagni() const {// ld ret = (ld)(limit_microsec - getMicrosec()) / limit_microsec;// return ret;// }// #else// const std::uint64_t CTimer::ClocksPerMicrosec = 2987;// std::uint64_t CTimer::getClocks() const {// unsigned int lo, hi;// __asm__ volatile ("rdtsc" : "=a" (lo), "=d" (hi));// return ((std::uint64_t)hi << 32) | lo;// }// CTimer::CTimer()// : start_clocks(getClocks()), limit_clocks(start_clocks) {// }// void CTimer::set(std::int64_t time_microsec) {// limit_clocks += time_microsec * ClocksPerMicrosec;// }// bool CTimer::elapsed() const {// return getClocks() >= limit_clocks;// }// std::int64_t CTimer::getMicrosec() const {// return (getClocks() - start_clocks) / ClocksPerMicrosec;// }// ld CTimer::GetClocksMagni() const {// ld ret = (ld)(limit_clocks - getClocks()) / (limit_clocks-start_clocks);// return ret;// }// #endifstruct state{int l,r,i;state(int l=0,int r=0,int i=0) : l(l),r(r),i(i) {}bool operator<(state const &ot) const{return r < ot.r;}};void solve(){int n,m,q; cin>>n>>m>>q;vi p(n);vs s(n);vi part(m,1);rep(i,n){// scanf("%d",&p[i]);cin>>p[i];p[i]--;cin>>s[i];if (s[i]=="AC") part[p[i]]++;}// rep(i,n){// cin>>p[i],p[i]--;// cin>>s[i];// }vpii ans(q);ll D = ceill((long double)n/sqrtl((long double)q));int maxc = n/D;vector<vector<state>> pock(maxc+1);rep(i,q){int l,r; cin>>l>>r;l--; r--;pock[l/D].pb(state(l,r,i));}// ll now=0;int kind_ac = 0;int sum_wa = 0;vi cnt_ac(m);vvi cnt_wa(m);rep(i,m) cnt_wa[i] = vi(part[i]);vi wl(m),wr(m);int l=0,r=-1;int& px = p[++r];if (s[r]=="AC"){if (++cnt_ac[px]==1){kind_ac++;sum_wa += cnt_wa[px][wl[px]];}wr[px]++;}else{cnt_wa[px][wr[px]]++;}rep(i,maxc+1){if (i%2 == 0){sort(rng(pock[i]));}else{sort(rrng(pock[i]));}fore(y , pock[i]){while (y.r > r){int px = p[++r];if (s[r]=="AC"){if (++cnt_ac[px]==1){kind_ac++;sum_wa += cnt_wa[px][wl[px]];}wr[px]++;}else{cnt_wa[px][wr[px]]++;}}while (y.l < l){int px = p[--l];if (s[l]=="AC"){if (++cnt_ac[px]==1){kind_ac++;}else{sum_wa -= cnt_wa[px][wl[px]];}wl[px]--;}else{if (cnt_ac[px]) sum_wa++;cnt_wa[px][wl[px]]++;}}while(y.r < r){int px = p[r];if (s[r--]=="AC"){if (--cnt_ac[px]==0){kind_ac--;sum_wa -= cnt_wa[px][wl[px]];}wr[px]--;}else{cnt_wa[px][wr[px]]--;}}while (y.l > l){int px = p[l];if (s[l++]=="AC"){if (--cnt_ac[px]==0){kind_ac--;}else{sum_wa += cnt_wa[px][wl[px]+1];}wl[px]++;}else{cnt_wa[px][wl[px]]--;if (cnt_ac[px]>0) sum_wa--;}}ans[y.i].fi = kind_ac;ans[y.i].se = sum_wa;}}rep(i,q) coutp(ans[i]);return;}int main(){ios::sync_with_stdio(false);cin.tie(0);// CTimer timer;int t = 1;//cin>>t;rep(i,t){solve();}// show(timer.getMicrosec());return 0;}