oj.uz

Submission #74727

# Submission time Handle Problem Language Result Execution time Memory
74727 2018-09-07T03:09:51 Z goodbaton Pairs (IOI07_pairs) C++14
70 / 100
 259 ms 36476 KB 
#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;
}

Compilation message

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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 484 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 592 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1304 KB Output is correct
2 Correct 26 ms 1704 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 2492 KB Output is correct
2 Correct 33 ms 3352 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 4232 KB Output is correct
2 Correct 34 ms 5096 KB Output is correct
3 Correct 33 ms 5968 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6592 KB Output is correct
2 Correct 4 ms 6668 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 28244 KB Output is correct
2 Correct 109 ms 28896 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 29596 KB Output is correct
2 Correct 223 ms 30416 KB Output is correct
3 Correct 180 ms 31300 KB Output is correct
4 Correct 196 ms 32000 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 33056 KB Output is correct
2 Correct 251 ms 34200 KB Output is correct
3 Correct 155 ms 35340 KB Output is correct
4 Correct 157 ms 36476 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 36476 KB Output is correct
2 Correct 5 ms 36476 KB Output is correct

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 36476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 36476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 36476 KB Output isn't correct
2 Halted 0 ms 0 KB -