QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#331610#6136. AirdropLainAC ✓991ms16484kbC++233.2kb2024-02-18 15:50:172024-02-18 15:50:17

Judging History

你现在查看的是最新测评结果

  • [2024-02-18 15:50:17]
  • 评测
  • 测评结果:AC
  • 用时:991ms
  • 内存:16484kb
  • [2024-02-18 15:50:17]
  • 提交

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