QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#274629 | #6136. Airdrop | C1942huangjiaxu | WA | 478ms | 14800kb | C++14 | 1.4kb | 2023-12-03 19:08:51 | 2023-12-03 19:08:51 |
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;
int tt=0;
void solve(){
++tt;
scanf("%d%d",&n,&Y0);
if(tt==57)printf("!%d %d\n",n,Y0);
for(int i=1;i<=n;++i){
scanf("%d%d",&p[i].x,&p[i].y);
if(tt==57)printf("%d %d\n",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]);
if(tt<=3)printf("%d %d\n",mn,mx);
}
int main(){
scanf("%d",&T);
while(T--)solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 6096kb
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: 478ms
memory: 14800kb
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 !6 6 7 6 10 6 5 10 1 8 3 4 6 5
result:
wrong output format Expected integer, but "!6" found