제출 #74727

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
74727		goodbaton	Pairs (IOI07_pairs)	C++14	70 / 100	259 ms	36476 KiB

pairs

#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long ll;

#define SIZE 100010
#define INF 1000000000

struct NODE{
  vector<int> vec;
  int l;
  int r;
  
  NODE():l(INF),r(INF){}
};

struct SEG1{
  vector<NODE> data;
  int segn2;

  void marge(NODE &res, NODE &a, NODE &b){
    int s=0,t=0;

    res.l = a.l;
    res.r = b.r;
    
    while(1){
      if(s<a.vec.size() && t<b.vec.size()){
	if(a.vec[s] < b.vec[t]){
	  res.vec.push_back(a.vec[s++]);
	}else{
	  res.vec.push_back(b.vec[t++]);
	}
      }else if(s<a.vec.size()){
	res.vec.push_back(a.vec[s++]);
      }else if(t<b.vec.size()){
	res.vec.push_back(b.vec[t++]);
      }else{
	break;
      }
    }
  }
  
  void init(int n,pair<int,int> *p){
    for(segn2=1;segn2<n;segn2*=2);

    data.assign(segn2*2,NODE());

    for(int i=0;i<n;i++){
      data[segn2+i-1].l = data[segn2+i-1].r = p[i].first;
      data[segn2+i-1].vec.push_back(p[i].second);
    }

    for(int i = segn2-2;i>=0;i--){
      marge(data[i],data[i*2+1],data[i*2+2]);
    }
  }

  ll query(int a,int b,int u,int v,int k=0){
    
    if(a<=data[k].l && data[k].r<=b){
      return upper_bound(data[k].vec.begin(),data[k].vec.end(),v) - lower_bound(data[k].vec.begin(),data[k].vec.end(),u);
    }

    if(data[k].r<a || b<data[k].l) return 0;

    return query(a,b,u,v,k*2+1) + query(a,b,u,v,k*2+2);
  } 
};

int b,n,d;

inline ll dis(ll a,ll b,ll c){
  return abs(a) + abs(b) + abs(c);
}

ll calc_0(){
  int p[SIZE][3] = {};
  ll ans = 0;
  
  for(int i=0;i<n;i++){
    for(int j=0;j<b;j++){
      scanf("%d",p[i]+j);
    }
  }

  for(int i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
      if(dis(p[i][0]-p[j][0],p[i][1]-p[j][1],p[i][2]-p[j][2]) <= d) ans++;
    }
  }

  return ans;
}

ll calc_1(){
  int p[SIZE];
  ll ans = 0;
  
  for(int i=0;i<n;i++){
    scanf("%d",p+i);
  }

  sort(p,p+n);

  for(int i=0;i<n;i++){
    ans += upper_bound(p,p+n,p[i]+d) - lower_bound(p,p+n,p[i]-d) - 1;
  }

  return ans/2;
}

ll calc_2(){
  int x[SIZE],y[SIZE];
  pair<int,int> p[SIZE];;
  SEG1 seg;
  ll ans = 0;
  
  for(int i=0;i<n;i++){
    scanf("%d%d",x+i,y+i);
    p[i] = {x[i] + y[i],x[i] - y[i]};
  }

  sort(p,p+n);
  
  seg.init(n,p);

  for(int i=0;i<n;i++){
    ans += seg.query(p[i].first-d,p[i].first+d,p[i].second-d,p[i].second+d) - 1;
  }

  return ans/2;
} 

int main(){
  ll ans = 0;
  int m;
  
  scanf("%d%d%d%d",&b,&n,&d,&m);

  if(b==1) ans = calc_1();
  else if(b==2) ans = calc_2();
  else if(n <= 1000) ans = calc_0();

  printf("%lld\n",ans);

  return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

pairs.cpp: In member function 'void SEG1::marge(NODE&, NODE&, NODE&)':
pairs.cpp:31:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if(s<a.vec.size() && t<b.vec.size()){
          ~^~~~~~~~~~~~~
pairs.cpp:31:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if(s<a.vec.size() && t<b.vec.size()){
                            ~^~~~~~~~~~~~~
pairs.cpp:37:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       }else if(s<a.vec.size()){
                ~^~~~~~~~~~~~~
pairs.cpp:39:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       }else if(t<b.vec.size()){
                ~^~~~~~~~~~~~~
pairs.cpp: In function 'll calc_0()':
pairs.cpp:86:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d",p[i]+j);
       ~~~~~^~~~~~~~~~~~~
pairs.cpp: In function 'll calc_1()':
pairs.cpp:104:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",p+i);
     ~~~~~^~~~~~~~~~
pairs.cpp: In function 'll calc_2()':
pairs.cpp:123:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",x+i,y+i);
     ~~~~~^~~~~~~~~~~~~~~~
pairs.cpp: In function 'int main()':
pairs.cpp:142:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d",&b,&n,&d,&m);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 6 / 6
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 6 / 6
• Subtask 6: 7 / 7
• Subtask 7: 7 / 7
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 10 / 10
• Subtask 11: 0 / 10
• Subtask 12: 0 / 10
• Subtask 13: 0 / 10