Submission #34645408

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
int read(){int r;scanf("%d",&r);return r;}

const int N=2e5;
pair<int,int> a[N+10];
vector<int> tr[N+10];
int n;

// [i-(i&(i-1))+1,i] 信息
void add(int x,int y) {
  for(int i=x;i<=N+1;i+=(i&-i)) tr[i].push_back(y);
}

int sum(int x,int l,int r) { // [l,r]
  int res=0;
  for(int i=x;i     ;i-=(i&-i)) res += upper_bound(tr[i].begin(),tr[i].end(),r)   //  (first >  r)
                                      -lower_bound(tr[i].begin(),tr[i].end(),l); // - (first >= l)
  return res;
}

bool check(int x,int y,int k,int d){
  int x0 = max(1  ,x-d);
  int x1 = min(N+1,x+d);
  int y0 = y-d;
  int y1 = y+d;
  // 求 x\in[x0,x1], y\in[y0,y1]
  return (sum(x1,y0,y1)-sum(x0-1,y0,y1)) >= k;
}

int main() {
  int n = read();
  rep(i,0,n){
    int x = read()+1; // 全部x+=1 保证 2e5+1 >= x+y >= 1
    int y = read();
    a[i] = {x+y,x-y};
  }
  sort(a,a+n,[](auto v0,auto v1){return v0.second < v1.second;});// 统一排序,让树状数组内的 值从小到大
  rep(i,0,n) add(a[i].first,a[i].second);
  int q = read();
  while(q--) {
    int x = read()+1; // 全部x+=1
    int y = read();
    int k = read();
    if(check(x+y,x-y,k,0)){
      printf("%d\n",0);
      continue;
    }
    int l=0,r=2e5+10; // 二分范围, l: <k个, r: >= k个
    while(l+1<r) {
      int mid=(l+r)/2;
      (check(x+y,x-y,k,mid)?r:l) = mid;
    }
    printf("%d\n",r);
  }
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int read()’:
./Main.cpp:4:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    4 | int read(){int r;scanf("%d",&r);return r;}
      |                  ~~~~~^~~~~~~~~

Judge Result