QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#105374 | #6136. Airdrop | Sorting# | TL | 2ms | 3408kb | C++ | 1.9kb | 2023-05-13 23:27:46 | 2023-05-13 23:27:48 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int N=2e5+1;
#define fi first
#define se second
int n;
ll x[N],y[N];
map<ll,vector<int> >mp;
map<ll,int>dx;
void add(ll l,ll r,ll v){
//cout << "add " << l << ' ' << r << ' ' << v << endl;
if(l>r) return;
dx[l]+=v;
dx[r+1]-=v;
}
void solve(){
ll y0;
cin >> n >> y0;
mp.clear();dx.clear();
for(int i=1; i<=n ;i++){
cin >> x[i] >> y[i];
y[i]-=y0;
mp[-x[i]+abs(y[i])].push_back(i);
}
for(auto &e:mp){
//cout << "doingL " << e.fi << endl;
auto &c=e.se;
vector<pair<int,int> >v;
for(auto d:c) v.push_back({x[d],d});
sort(v.begin(),v.end());
int chp=0;
for(int i=0; i<v.size() ;i++){
if(i!=v.size()-1 && v[i+1].fi==v[i].fi) continue;
ll cur=v[i].fi;
ll nxt=2e18;
if(i+1!=v.size()) nxt=v[i+1].fi;
if(i>0 && v[i-1].fi==v[i].fi){
add(cur,cur,2+chp);
add(cur+1,nxt-1,0);
chp=0;
}
else{
add(cur,cur,chp+1);
chp^=1;
add(cur+1,nxt-1,chp);
}
}
}
mp.clear();
for(int i=1; i<=n ;i++){
mp[x[i]+abs(y[i])].push_back(i);
}
for(auto &e:mp){
//cout << "doingR " << e.fi << endl;
auto &c=e.se;
vector<pair<int,int> >v;
for(auto d:c) v.push_back({x[d],d});
sort(v.begin(),v.end());
reverse(v.begin(),v.end());
int chp=0;
for(int i=0; i<v.size() ;i++){
if(i!=v.size()-1 && v[i+1].fi==v[i].fi) continue;
ll cur=v[i].fi;
ll nxt=-2e18;
if(i+1!=v.size()) nxt=v[i+1].fi;
if(i>0 && v[i-1].fi==v[i].fi){
add(cur,cur,chp);
add(nxt+1,cur-1,0);
chp=0;
}
else{
add(cur,cur,chp);
chp^=1;
add(nxt+1,cur-1,chp);
}
}
}
ll cur=0;
ll mn=2e18;
ll mx=-2e18;
for(auto d:dx){
if(d.fi>1.5e18) break;
cur+=d.se;
mn=min(mn,cur);
mx=max(mx,cur);
}
cout << mn << ' ' << mx << '\n';
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);
int t;cin >> t;
while(t--) solve();
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 3408kb
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
Time Limit Exceeded
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 4 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 ...