QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#94109 | #6136. Airdrop | ksunhokim | RE | 0ms | 0kb | C++20 | 1.3kb | 2023-04-05 13:55:00 | 2023-04-05 13:55:04 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
int n, y0;
cin >> n >> y0;
const int N = 1e5;
vector<int> pos;
vector<int> X(n), Y(n);
for (int i=0;i<n;i++){
cin >> X[i] >> Y[i];
}
vector<vector<int>> pts(N+10);
map<int, int> cnt;
ll cur = 0;
for (int i=0;i<n;i++){
int d = abs(Y[i] - y0);
pts[X[i]].push_back(d);
cnt[X[i]+d]++;
if (cnt[X[i]+d] == 1) {
cur++;
}
if (cnt[X[i]+d] == 2) {
cur--;
}
pos.push_back(X[i]);
pos.push_back(X[i]+1);
}
pos.push_back(0);
sort(begin(pos), end(pos));
pos.resize(unique(begin(pos), end(pos))- begin(pos));
ll mx = -1, mn = 1e18+1;
mx = max(mx, cur);
mn = min(mn, cur);
for (int x0 : pos){
for (int d : pts[x0-1]) {
cur--;
cnt[x0-1-d]++;
if (cnt[x0-1-d] == 1) {
cur++;
}
if (cnt[x0-1-d] == 2) {
cur--;
}
}
for (int d : pts[x0]) {
if (cnt[x0+d] == 2) {
cur++;
}
if (cnt[x0+d] == 1) {
cur--;
}
cnt[x0+d]--;
cur++;
}
mx = max(mx, cur);
mn = min(cur, mn);
}
cout << mn << " " << mx << "\n";
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int t;
cin >> t;
while(t--)
solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
3 3 2 1 2 2 1 3 5 3 3 2 1 2 5 4 3 2 3 1 3 4 3