QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#94109#6136. AirdropksunhokimRE 0ms0kbC++201.3kb2023-04-05 13:55:002023-04-05 13:55:04

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 13:55:04]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-04-05 13:55:00]
  • 提交

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

output:


result: