Submission #113421

#	Time	Username	Problem	Language	Result	Execution time	Memory
113421		TadijaSebez	Pairs (IOI07_pairs)	C++11	60 / 100	173 ms	27132 KiB

pairs

#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 (stderr)

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 / 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: 0 / 10
• Subtask 11: 0 / 10
• Subtask 12: 0 / 10
• Subtask 13: 0 / 10