QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#718965 | #6439. Cloud Retainer's Game | frogman | WA | 742ms | 15264kb | C++14 | 1.8kb | 2024-11-06 21:56:05 | 2024-11-06 21:56:08 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+100;
int H,n,m,f[N][2],cnt;
map<int,int> t0;
map<int,int> t1;
map<int,int> num0;
map<int,int> num1;
map<int,int> f0;
map<int,int> f1;
struct node
{
int x,y,flag;
}c[N];
bool cmp(node a,node b){
if(a.x==b.x) return a.y<b.y;
return a.x<b.x;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int T;
cin>>T;
while(T--)
{
cin>>H;
cin>>n;
cnt=0;
for(int i=1;i<=n;i++)
{
int x,y;
cin>>x>>y;
c[++cnt].flag=0;
c[cnt].x=x;c[cnt].y=y;
}
cin>>m;
for(int j=1;j<=m;j++)
{
int x,y;
cin>>x>>y;
c[++cnt].flag=1;
c[cnt].x=x;c[cnt].y=y;
}
sort(c+1,c+1+cnt,cmp);
f[n+1][0]=0;
int ans=0;
t0[0]=n+1;
t1[0]=n+1;
for(int i=1;i<=cnt;i++)
{
int x=c[i].x%(2*H),y=c[i].y;
if(c[i].flag==0)
{
if(t0[x-y])
{
f[i][0]=f[t0[x-y]][0]+num0[x-y];
}
else if(t1[x-y])
{
f[i][0]=f[t1[x-y]][1]+num1[x-y]+num0[x-y];
}
if(t1[x+y])
{
f[i][1]=f[t1[x+y]][1]+num1[x+y];
}
else if(t0[x+y-2*H])
{
f[i][1]=f[t0[x+y-2*H]][0]+num0[x+y-2*H]+num1[x+y];
}
t0[x-y]=i;
t1[x+y]=i;
num0[x-y]=0;
num1[x+y]=0;
f0[x-y]=max(f0[x-y],f[i][0]);
f1[x+y]=max(f1[x+y],f[i][1]);
ans=max(ans,max(f[i][0],f[i][1]));
}
else
{
num0[x-y]++;
num1[x+y]++;
}
}
for(int i=cnt;i>=1;i--)
{
if(c[i].flag==1) continue;
int x=c[i].x%(2*H),y=c[i].y;
ans=max(ans,f0[x-y]+num0[x-y]);
ans=max(ans,f1[x-y]+num1[x-y]+num0[x-y]);
ans=max(ans,f1[x+y]+num1[x+y]);
ans=max(ans,f0[x+y-2*H]+num0[x+y-2*H]+num1[x+y]);
}
cout<<ans<<"\n";
num0.clear();num1.clear();
t0.clear();t1.clear();
f0.clear();f1.clear();
}
}
/*
1
3
1
4 2
3
1 1
6 2
9 1
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5648kb
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: 742ms
memory: 15264kb
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 2 3 3 3 3 3 2 2 1 2 2 3 2 3 2 2 2 2 4 2 2 3 0 3 3 2 2 2 1 4 4 3 2 1 2 2 3 4 2 3 1 3 2 1 0 2 2 4 2 2 3 1 2 1 3 4 3 3 4 2 2 1 3 2 2 4 1 2 1 3 2 3 2 1 1 4 5 1 2 1 1 4 2 3 0 1 3 1 2 4 2 2 1 2 4 4 3 4 5 2 2 4 2 4 3 4 2 2 1 2 2 2 4 2 2 3 0 2 3 2 4 2 3 1 2 3 1 2 3 2 4 2 2 1 4 4 2 2 2 3 1 2 3 0 4 3 ...
result:
wrong answer 5th numbers differ - expected: '3', found: '2'