QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#610704 | #6439. Cloud Retainer's Game | ucup-team4352# | WA | 639ms | 7820kb | C++23 | 2.1kb | 2024-10-04 17:01:40 | 2024-10-04 17:01:41 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define lowbit(x) (x&-x)
#define log(x) (31^__builtin_clz(x))
using namespace std;
const int maxn=2e5+5;
pii w[maxn],c[maxn];
map<int,int>dp1,dp2;
vector<pii>op1,op2;
void upd(){
for(auto u:op1){
dp1[u.first]=max(dp1[u.first],u.second);
}
for(auto u:op2){
dp2[u.first]=max(dp2[u.first],u.second);
}
op1.clear();
op2.clear();
}
void solve(){
int n,m,h;
cin>>h>>n;
for(int i=1;i<=n;i++){
cin>>w[i].first>>w[i].second;
w[i+n]={w[i].first,2*h-w[i].second};
}
cin>>m;
for(int i=1;i<=m;i++){
cin>>c[i].first>>c[i].second;
c[i+m]={c[i].first,2*h-c[i].second};
}
n<<=1;
m<<=1;
sort(w+1,w+n+1);
sort(c+1,c+m+1);
w[n+1].first=-1;
c[m+1].first=-1;
int now=m,lst=-1;
dp1.clear();
dp2.clear();
op1.clear();
op2.clear();
for(int i=n;i>=1;i--){
while(now&&c[now].first>=w[i].first){
if(c[now].first!=lst)upd();
lst=c[now].first;
int tmp=(1ll*c[now].first-c[now].second)%(2*h);
if(tmp<0)tmp+=2*h;
op1.push_back({tmp,dp1[tmp]+1});
tmp=(1ll*c[now].first+c[now].second)%(2*h);
op2.push_back({tmp,dp2[tmp]+1});
now--;
}
if(w[i].first!=lst)upd();
lst=w[i].first;
int z=(w[i].first-w[i].second)%(2*h),f=(1ll*w[i].first+w[i].second)%(2*h);
if(z<0)z+=2*h;
op1.push_back({z,dp2[f]});
op2.push_back({f,dp1[z]});
}
while(now){
if(c[now].first!=lst)upd();
lst=c[now].first;
int tmp=c[now].first-c[now].second;
if(tmp<0)tmp+=2*h;
op1.push_back({tmp,dp1[tmp]+1});
tmp=(1ll*c[now].first+c[now].second)%(2*h);
op2.push_back({tmp,dp2[tmp]+1});
now--;
}
upd();
cout<<dp1[0]<<"\n";
}
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t=1;
cin>>t;
while(t--)solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5756kb
input:
2 4 3 1 1 2 2 6 2 4 3 1 3 3 5 1 7 3 3 1 4 2 3 1 1 6 2 9 1
output:
3 3
result:
ok 2 number(s): "3 3"
Test #2:
score: -100
Wrong Answer
time: 639ms
memory: 7820kb
input:
5503 10 19 2 4 2 8 8 3 8 4 8 7 2 7 2 6 1 5 3 2 6 4 2 1 4 5 2 5 7 1 4 7 5 7 2 2 8 6 8 1 12 5 1 4 8 5 2 6 1 3 6 1 1 1 7 7 2 5 6 6 8 1 2 3 5 10 5 9 5 10 7 6 6 5 7 1 3 9 6 8 8 8 6 4 2 9 5 4 4 2 10 9 2 3 2 1 7 1 4 3 14 4 6 6 1 2 1 7 6 2 3 4 4 5 3 6 5 1 4 3 4 3 2 6 2 8 6 8 2 6 6 5 2 5 1 3 1 2 3 7 4 5 5 3 ...
output:
2 1 2 1 3 2 0 2 4 6 1 2 0 0 1 2 1 1 0 1 0 0 2 1 1 3 2 3 3 2 1 2 0 1 5 1 1 1 0 1 3 1 2 3 3 3 2 1 0 3 1 2 2 0 4 1 1 0 1 2 2 2 1 1 1 1 2 3 2 2 2 1 1 3 1 3 0 0 3 4 5 1 1 1 1 1 0 2 0 0 3 0 2 1 1 1 0 3 2 1 3 4 3 2 2 4 2 4 2 1 2 1 0 1 3 0 3 0 2 1 0 2 5 1 2 2 1 0 1 3 0 2 3 1 4 2 2 0 2 3 2 0 0 3 1 1 1 1 3 2 ...
result:
wrong answer 2005th numbers differ - expected: '5', found: '4'