QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#94115#6136. AirdropksunhokimTL 8ms9708kbC++201.4kb2023-04-05 14:03:142023-04-05 14:03:17

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-05 14:03:17]
  • 评测
  • 测评结果:TL
  • 用时:8ms
  • 内存:9708kb
  • [2023-04-05 14:03:14]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve() {
  int n, y0;
  cin >> n >> y0;
  const int N = 2e5 + 1000;
  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);
  vector<int> cnt(2*N);
  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+N]++;
    if (cnt[X[i]+d+N] == 1) {
      cur++;
    }
    if (cnt[X[i]+d+N] == 2) {
      cur--;
    }
    pos.push_back(X[i]);
    pos.push_back(X[i]+1);
  }
  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+N]++;
      if (cnt[x0-1-d+N] == 1) {
        cur++;
      }
      if (cnt[x0-1-d+N] == 2) {
        cur--;
      }
    }
    for (int d : pts[x0]) {
      if (cnt[x0+d+N] == 2) {
        cur++;
      }
      if (cnt[x0+d+N] == 1) {
        cur--;
      }
      cnt[x0+d+N]--;
      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(); 
    if (t == 100)
      break;
  }
}

詳細信息

Test #1:

score: 100
Accepted
time: 8ms
memory: 9708kb

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
3 7
4 4
9 9
4 6
0 3
1 6
2 2
2 6
10 10
9 9
1 3
2 4
0 2
1 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
3 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
1 4
1 ...

result: