QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#331610 | #6136. Airdrop | Lain | AC ✓ | 991ms | 16484kb | C++23 | 3.2kb | 2024-02-18 15:50:17 | 2024-02-18 15:50:17 |
Judging History
answer
#include "bits/stdc++.h"
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int tt;
cin >> tt;
while(tt--) {
int n, y0;
cin >> n >> y0;
vector<int> x(n), y(n), t(n);
vector<int> xs = {0};
xs.reserve(3*n+1);
// At key, these points become active.
map<int, vector<int>> events;
for (int i = 0; i < n; i++) {
cin >> x[i] >> y[i];
t[i] = abs(y[i] - y0);
xs.push_back(x[i]);
xs.push_back(x[i]-1);
xs.push_back(x[i]+1);
events[x[i]].push_back(i);
}
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
vector<int> from_left(xs.size()), from_right(xs.size());
// go from left
{
set<int> vals;
int active = 0;
for (int i =0; i < xs.size(); i++) {
int X = xs[i];
from_left[i] = active;
// at the end, add the points that become active here
auto it = events.find(X);
if (it == events.end()) continue;
active += it->second.size();
set<int> already_broken;
for (auto& j : it->second) {
int val = x[j] - t[j];
auto it = vals.find(val);
if (it == vals.end()) {
auto it = already_broken.find(val);
if (it != already_broken.end()) {
// This is being destroyed in the same point.
active--;
} else {
vals.insert(val);
}
} else {
already_broken.insert(val);
vals.erase(it);
active -= 2;
}
}
}
}
// go from right
{
set<int> vals;
int active = 0;
for (int i = (int)xs.size() - 1; i >=0; i--) {
int X = xs[i];
from_right[i] = active;
// at the end, add the points that become active here
auto it = events.find(X);
if (it == events.end()) continue;
active += it->second.size();
set<int> already_broken;
for (auto& j : it->second) {
int val = x[j] + t[j];
auto it = vals.find(val);
if (it == vals.end()) {
auto it = already_broken.find(val);
if (it != already_broken.end()) {
// This is being destroyed in the same point.
active--;
} else {
vals.insert(val);
}
} else {
already_broken.insert(val);
vals.erase(it);
active -= 2;
}
}
}
}
/* for (auto& x : xs) cout << x << " "; */
/* cout << '\n'; */
/* for (auto& x : xs) cout << x << " "; */
/* cout << '\n'; */
int minans = 1e9, maxans =0;
for (int i = 0; i < xs.size(); i++) {
minans = min(minans, (int)events[xs[i]].size() + from_left[i] + from_right[i]);
maxans = max(maxans, (int)events[xs[i]].size() + from_left[i] + from_right[i]);
}
cout << minans << " " << maxans << '\n';
}
}
// Iterate from left to right, then right to left
// for l2r, keep track of x[i] - t[i]
// for r2l, keep track of x[i] + t[i];
// Consider x = 0, x = x[i] - 1, x = x[i], x = x[i]+1
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3804kb
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: 0
Accepted
time: 991ms
memory: 16484kb
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 ...
result:
ok 7016 numbers