Submission #113426

#	Time	Username	Problem	Language	Result	Execution time	Memory
113426		TadijaSebez	Pairs (IOI07_pairs)	C++11	60 / 100	166 ms	26036 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);
}
const int H=77*3;
struct BIT3D
{
	int sum[H][H][H];
	BIT3D(){}
	void Add(int x, int y, int z, int f)
	{
		for(int i=x;i<H;i+=i&-i)
			for(int j=y;j<H;j+=j&-j)
				for(int k=z;k<H;k+=k&-k)
					sum[i][j][k]+=f;
	}
	int Get(int x, int y, int z)
	{
		int ans=0;
		for(int i=x;i;i-=i&-i)
			for(int j=y;j;j-=j&-j)
				for(int k=z;k;k-=k&-k)
					ans+=sum[i][j][k];
		return ans;
	}
	int Get(int xl, int xr, int yl, int yr, int zl, int zr)
	{
		xl--;yl--;zl--;
		xl=max(0,xl);
		yl=max(0,yl);
		zl=max(0,zl);
		xr=min(xr,H-1);
		yr=min(yr,H-1);
		zr=min(zr,H-1);
		return Get(xr,yr,zr)-Get(xl,yr,zr)-Get(xr,yl,zr)-Get(xr,yr,zl)+Get(xl,yl,zr)+Get(xl,yr,zl)+Get(xr,yl,zl)-Get(xl,yl,zl);
	}
} ST;
int z[N];
void Solve3D()
{
	int n,d,m,i;
	scanf("%i %i %i",&n,&d,&m);
	for(i=1;i<=n;i++)
	{
		scanf("%i %i %i",&x[i],&y[i],&z[i]);
		id[i]=i;
	}
	sort(id+1,id+1+n,[&](int i, int j){ return x[i]+y[i]+z[i]<x[j]+y[j]+z[j];});
	int l=1;
	ll ans=0;
	for(int j=1;j<=n;j++)
	{
		int i=id[j];
		while(x[i]+y[i]+z[i]-x[id[l]]-y[id[l]]-z[id[l]]>d)
		{
			int k=id[l];
			ST.Add(n-x[k]+y[k]+z[k],n+x[k]-y[k]+z[k],n+x[k]+y[k]-z[k],-1);
			l++;
		}
		ans+=ST.Get(n-x[i]+y[i]+z[i]-d,n-x[i]+y[i]+z[i]+d,n+x[i]-y[i]+z[i]-d,n+x[i]-y[i]+z[i]+d,n+x[i]+y[i]-z[i]-d,n+x[i]+y[i]-z[i]+d);
		ST.Add(n-x[i]+y[i]+z[i],n+x[i]-y[i]+z[i],n+x[i]+y[i]-z[i],1);
	}
	printf("%lld\n",ans);
}
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 'void Solve3D()':
pairs.cpp:94: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:97:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i %i",&x[i],&y[i],&z[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp: In function 'int main()':
pairs.cpp:120: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