oj.uz

Submission #379295

# Submission time Handle Problem Language Result Execution time Memory
379295 2021-03-17T21:55:51 Z MilosMilutinovic Pairs (IOI07_pairs) C++14
60 / 100
 46 ms 4076 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n,d,m;
void Solve1D(){
    vector<int> x(n);
    for(int i=0;i<n;i++)scanf("%i",&x[i]);
    sort(x.begin(),x.end());
    ll ans=0;
    for(int i=0;i<n;i++){
        int bot=i,top=n-1,pos=i;
        while(bot<=top){
			int mid=bot+top>>1;
            if(x[mid]-x[i]<=d)pos=mid,bot=mid+1;
            else top=mid-1;
        }
        ans+=pos-i;
    }
    printf("%lld",ans);
}
const int N=200050;
int bit[N];
void Add(int x,int f){
    for(;x<N;x+=x&-x){
        bit[x]+=f;
    }
}
int Get(int x){
    int res=0;
    for(;x;x-=x&-x){
		res+=bit[x];
    }
    return res;
}
void Solve2D(){
    vector<int> x(n),y(n),sum(n),dif(n);
    for(int i=0;i<n;i++)scanf("%i%i",&x[i],&y[i]),sum[i]=x[i]+y[i],dif[i]=x[i]-y[i];
    vector<int> id(n);
    iota(id.begin(),id.end(),0);
    sort(id.begin(),id.end(),[&](int i,int j){
        return dif[i]<dif[j];
	});
    int j=0;
    ll ans=0;
    for(int i=0;i<n;i++){
        while(dif[id[i]]-dif[id[j]]>d){
            Add(sum[id[j]],-1);
			j++;
        }
        ans+=Get(min(N-1,sum[id[i]]+d))-Get(max(1,sum[id[i]]-d-1));
        Add(sum[id[i]],1);
    }
    printf("%lld",ans);
}
int main(){
	int b;scanf("%i%i%i%i",&b,&n,&d,&m);
    if(b==1)Solve1D();
    if(b==2)Solve2D();
    //if(b==3)Solve3D();
}

Compilation message

pairs.cpp: In function 'void Solve1D()':
pairs.cpp:13:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   13 |    int mid=bot+top>>1;
      |            ~~~^~~~
pairs.cpp:7:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    7 |     for(int i=0;i<n;i++)scanf("%i",&x[i]);
      |                         ~~~~~^~~~~~~~~~~~
pairs.cpp: In function 'void Solve2D()':
pairs.cpp:37:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |     for(int i=0;i<n;i++)scanf("%i%i",&x[i],&y[i]),sum[i]=x[i]+y[i],dif[i]=x[i]-y[i];
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~
pairs.cpp: In function 'int main()':
pairs.cpp:56:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   56 |  int b;scanf("%i%i%i%i",&b,&n,&d,&m);
      |        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 748 KB Output is correct
2 Correct 18 ms 748 KB Output is correct

Subtask #4
6.0 / 6.0

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

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 748 KB Output is correct
2 Correct 25 ms 748 KB Output is correct
3 Correct 24 ms 748 KB Output is correct

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 2924 KB Output is correct
2 Correct 31 ms 2924 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 3072 KB Output is correct
2 Correct 37 ms 3052 KB Output is correct
3 Correct 36 ms 3052 KB Output is correct
4 Correct 37 ms 3052 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 3948 KB Output is correct
2 Correct 44 ms 3948 KB Output is correct
3 Correct 46 ms 4076 KB Output is correct
4 Correct 46 ms 3948 KB Output is correct

Subtask #10
0 / 10.0

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

Subtask #11
0 / 10.0

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

Subtask #12
0 / 10.0

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

Subtask #13
0 / 10.0

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