QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#718920 | #6439. Cloud Retainer's Game | frogman | TL | 1ms | 5688kb | C++14 | 1.8kb | 2024-11-06 21:47:01 | 2024-11-06 21:47:02 |
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;
int tot=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;
for(int i=1;i<=cnt;i++)
{
int x=c[i].x%(2*H),y=c[i].y;
if(c[i].flag==1)
{
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();
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5688kb
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
Time Limit Exceeded
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 ...