結果

問題 No.2338 Range AtCoder Query
ユーザー Rubikun
提出日時 2023-06-02 22:24:37
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,514 bytes
コンパイル時間 8,384 ms
コンパイル使用メモリ 280,156 KB
最終ジャッジ日時 2025-02-13 19:02:01
ジャッジサーバーID
(参考情報)
judge5 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 30 TLE * 4
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=200005,INF=1<<30;
struct dat{
int l;
int r;
int id;
};
deque<int> AC[MAX],WA[MAX];
const int D=500;
int main(){
std::ifstream in("text.txt");
std::cin.rdbuf(in.rdbuf());
cin.tie(0);
ios::sync_with_stdio(false);
int N,M,Q;cin>>N>>M>>Q;
vector<int> A(N);
for(int i=0;i<N;i++){
int x;cin>>x;x--;
string S;cin>>S;
if(S=="AC") A[i]=x;
else A[i]=~x;
}
int l=-1,r=-1;
vector<dat> S(Q);
vector<pair<int,int>> ans(Q);
for(int i=0;i<Q;i++){
cin>>S[i].l>>S[i].r;
S[i].l--;
S[i].r--;
S[i].id=i;
}
vector<int> usel;
for(int i=0;i<Q;i++) usel.push_back(S[i].l/D);
sort(all(usel));
usel.erase(unique(all(usel)),usel.end());
vector<int> ty(N);
for(int i=0;i<si(usel);i++){
ty[usel[i]]=i&1;
}
sort(all(S),[&](auto a,auto b){
if(a.l/D==b.l/D){
if(ty[a.l/D]) return a.r>b.r;
else return a.r<b.r;
}
return a.l/D<b.l/D;
});
int ac=0,wa=0;
for(int i=0;i<Q;i++){
while(S[i].r>r){
r++;
if(A[r]>=0){
int x=A[r];
if(si(AC[x])==0){
wa+=si(WA[x]);
ac++;
}
AC[x].push_back(r);
}else{
int x=~A[r];
WA[x].push_back(r);
}
}
while(S[i].l<l){
l--;
if(A[l]>=0){
int x=A[l];
if(si(AC[x])>=1){
int ne=AC[x][0];
wa-=lower_bound(all(WA[x]),ne)-WA[x].begin();
}else{
ac++;
}
AC[x].push_front(l);
}else{
int x=~A[l];
if(si(AC[x])>=1){
wa++;
}
WA[x].push_front(l);
}
}
while(S[i].r<r){
if(A[r]>=0){
int x=A[r];
if(si(AC[x])==1){
wa-=si(WA[x]);
ac--;
}
AC[x].pop_back();
}else{
int x=~A[r];
WA[x].pop_back();
}
r--;
}
while(S[i].l>l){
if(l>=0){
if(A[l]>=0){
int x=A[l];
if(si(AC[x])==1){
ac--;
}else{
int ne=AC[x][1];
wa+=lower_bound(all(WA[x]),ne)-WA[x].begin();
}
AC[x].pop_front();
}else{
int x=~A[l];
if(si(AC[x])>=1){
wa--;
}
WA[x].pop_front();
}
}
l++;
}
ans[S[i].id]=mp(ac,wa);
//break;
}
for(int i=0;i<Q;i++) cout<<ans[i].fi<<" "<<ans[i].se<<"\n";
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0