QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#274627 | #6136. Airdrop | C1942huangjiaxu | WA | 500ms | 14912kb | C++14 | 1.3kb | 2023-12-03 19:07:07 | 2023-12-03 19:07:07 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int T,n,Y0,a[N],ca,mx,mn,pr[N],su[N];
vector<int>e[N];
struct po{
int x,y;
}p[N];
set<int>S;
void solve(){
scanf("%d%d",&n,&Y0);
for(int i=1;i<=n;++i){
scanf("%d%d",&p[i].x,&p[i].y);
p[i].y=abs(p[i].y-Y0);
a[i]=p[i].x;
}
sort(a+1,a+n+1);
ca=unique(a+1,a+n+1)-a-1;
for(int i=1;i<=ca;++i)e[i].clear();
for(int i=1;i<=n;++i){
p[i].x=lower_bound(a+1,a+ca+1,p[i].x)-a;
e[p[i].x].push_back(p[i].y);
}
for(int i=1;i<=ca;++i)sort(e[i].begin(),e[i].end());
mx=0,mn=n,su[ca+1]=0;
S.clear();
for(int i=1,ad=0;i<=ca;++i){
vector<int>g;
for(auto v:e[i]){
if(S.count(v-ad))g.push_back(v-ad);
S.insert(v-ad);
}
for(auto v:g)S.erase(v);
pr[i]=S.size();
ad+=a[i+1]-a[i];
}
S.clear();
for(int i=ca,ad=0;i;--i){
vector<int>g;
for(auto v:e[i]){
if(S.count(v-ad))g.push_back(v-ad);
S.insert(v-ad);
}
for(auto v:g)S.erase(v);
su[i]=S.size();
ad+=a[i]-a[i-1];
}
for(int i=1;i<=ca;++i){
mx=max(mx,pr[i-1]+su[i+1]+(int)e[i].size()),mn=min(mn,pr[i-1]+su[i+1]+(int)e[i].size());
mx=max(mx,pr[i-1]+su[i]),mn=min(mn,pr[i-1]+su[i]);
}
mx=max(mx,pr[ca]),mn=min(mn,pr[ca]);
printf("%d %d\n",mn,mx);
}
int main(){
scanf("%d",&T);
while(T--)solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 6228kb
input:
3 3 2 1 2 2 1 3 5 3 3 2 1 2 5 4 3 2 3 1 3 4 3
output:
1 3 0 3 2 2
result:
ok 6 numbers
Test #2:
score: -100
Wrong Answer
time: 500ms
memory: 14912kb
input:
3508 6 1 7 1 1 1 9 1 10 1 3 1 4 1 3 8 8 9 8 7 1 8 9 5 10 1 10 8 10 2 5 1 9 9 5 9 10 9 6 4 4 7 6 7 10 5 3 8 9 5 9 9 7 5 4 7 10 5 6 9 9 5 6 6 9 3 3 2 5 1 3 8 6 4 5 9 10 2 2 9 10 10 10 8 4 1 7 1 6 1 3 1 5 1 2 4 9 3 3 3 4 5 3 8 9 6 9 9 6 3 9 5 9 3 2 9 9 1 9 2 4 1 5 4 5 6 6 5 9 8 4 1 2 1 5 1 7 1 3 1 9 10...
output:
6 6 1 3 1 5 2 6 2 6 0 2 4 4 2 2 4 4 4 7 4 4 9 9 4 6 0 3 2 6 2 2 2 6 10 10 9 9 1 3 2 4 0 2 2 4 4 7 6 6 9 9 2 2 2 2 3 5 1 4 2 2 1 1 3 5 4 7 3 6 1 1 5 7 5 5 1 3 2 2 1 7 1 1 4 6 2 4 2 6 2 4 1 7 2 4 9 9 0 3 1 1 3 8 2 2 2 2 9 9 3 7 2 4 4 6 2 5 0 2 2 5 3 3 0 4 4 4 2 4 2 2 4 6 6 6 6 6 0 2 2 6 2 4 2 6 2 5 1 ...
result:
wrong answer 113th numbers differ - expected: '4', found: '2'