oj.uz

Submission #113421

# Submission time Handle Problem Language Result Execution time Memory
113421 2019-05-25T13:30:17 Z TadijaSebez Pairs (IOI07_pairs) C++11
60 / 100
 173 ms 27132 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
void Solve1D()
{
	int n,d,m,i;
	scanf("%i %i %i",&n,&d,&m);
	vector<int> x(n);
	for(int i=0;i<n;i++) scanf("%i",&x[i]);
	sort(x.begin(),x.end());
	int j=0;
	ll ans=0;
	for(int i=0;i<n;i++)
	{
		while(x[i]-x[j]>d) j++;
		ans+=i-j;
	}
	printf("%lld\n",ans);
}
const int N=100050;
const int lim=2*N;
int x[N],y[N],sum[N],dif[N],id[N];
const int M=20*N;
int ls[M],rs[M],tsz,root[N],cnt[M];
void Set(int p, int &c, int ss, int se, int qi, int f)
{
    c=++tsz;ls[c]=ls[p];rs[c]=rs[p];cnt[c]=cnt[p]+f;
    if(ss==se) return;
    int mid=ss+se>>1;
    if(qi<=mid) Set(ls[p],ls[c],ss,mid,qi,f);
    else Set(rs[p],rs[c],mid+1,se,qi,f);
}
int Get(int p, int c, int ss, int se, int qs, int qe)
{
	if(qs>qe || qs>se || ss>qe) return 0;
	if(qs<=ss && qe>=se) return cnt[c]-cnt[p];
	int mid=ss+se>>1;
	return Get(ls[p],ls[c],ss,mid,qs,qe)+Get(rs[p],rs[c],mid+1,se,qs,qe);
}
void Solve2D()
{
	int n,d,m,i;
	scanf("%i %i %i",&n,&d,&m);
	for(i=1;i<=n;i++) scanf("%i %i",&x[i],&y[i]),sum[i]=x[i]+y[i],dif[i]=x[i]-y[i],id[i]=i;
	sort(id+1,id+1+n,[&](int i, int j){ return sum[i]<sum[j];});
	int l=1;
	ll ans=0;
	for(int j=1;j<=n;j++)
	{
		i=id[j];
		Set(root[j-1],root[j],-lim,lim,dif[i],1);
		while(sum[i]-sum[id[l]]>d) l++;
		ans+=Get(root[l-1],root[j-1],-lim,lim,dif[i]-d,dif[i]+d);
	}
	printf("%lld\n",ans);
}
void Solve3D(){}
int main()
{
	int B;
	scanf("%i",&B);
	if(B==1) Solve1D();
	if(B==2) Solve2D();
	if(B==3) Solve3D();
	return 0;
}

Compilation message

pairs.cpp: In function 'void Solve1D()':
pairs.cpp:6:12: warning: unused variable 'i' [-Wunused-variable]
  int n,d,m,i;
            ^
pairs.cpp: In function 'void Set(int, int&, int, int, int, int)':
pairs.cpp:29:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=ss+se>>1;
             ~~^~~
pairs.cpp: In function 'int Get(int, int, int, int, int, int)':
pairs.cpp:37:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
pairs.cpp: In function 'void Solve1D()':
pairs.cpp:7:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i %i",&n,&d,&m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
pairs.cpp:9:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0;i<n;i++) scanf("%i",&x[i]);
                       ~~~~~^~~~~~~~~~~~
pairs.cpp: In function 'void Solve2D()':
pairs.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i %i",&n,&d,&m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
pairs.cpp:44:80: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1;i<=n;i++) scanf("%i %i",&x[i],&y[i]),sum[i]=x[i]+y[i],dif[i]=x[i]-y[i],id[i]=i;
                    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
pairs.cpp: In function 'int main()':
pairs.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&B);
  ~~~~~^~~~~~~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

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

Subtask #4
6.0 / 6.0

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

Subtask #5
6.0 / 6.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 26416 KB Output is correct
2 Correct 84 ms 26344 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 26564 KB Output is correct
2 Correct 113 ms 26508 KB Output is correct
3 Correct 108 ms 26540 KB Output is correct
4 Correct 98 ms 26688 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 27132 KB Output is correct
2 Correct 173 ms 26944 KB Output is correct
3 Correct 93 ms 26920 KB Output is correct
4 Correct 100 ms 26872 KB Output is correct

Subtask #10
0 / 10.0

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

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 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 256 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 256 KB Output isn't correct
2 Halted 0 ms 0 KB -