oj.uz

Submission #113427

# Submission time Handle Problem Language Result Execution time Memory
113427 2019-05-25T14:26:08 Z TadijaSebez Pairs (IOI07_pairs) C++11
100 / 100
 326 ms 25896 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);
}
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(m-x[k]+y[k]+z[k],m+x[k]-y[k]+z[k],m+x[k]+y[k]-z[k],-1);
			l++;
		}
		ans+=ST.Get(m-x[i]+y[i]+z[i]-d,m-x[i]+y[i]+z[i]+d,m+x[i]-y[i]+z[i]-d,m+x[i]-y[i]+z[i]+d,m+x[i]+y[i]-z[i]-d,m+x[i]+y[i]-z[i]+d);
		ST.Add(m-x[i]+y[i]+z[i],m+x[i]-y[i]+z[i],m+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

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.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 256 KB Output is correct

Subtask #3
6.0 / 6.0

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

Subtask #4
6.0 / 6.0

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

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 768 KB Output is correct
2 Correct 23 ms 768 KB Output is correct
3 Correct 22 ms 768 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 71 ms 25720 KB Output is correct
2 Correct 82 ms 25832 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 25788 KB Output is correct
2 Correct 104 ms 25896 KB Output is correct
3 Correct 96 ms 25820 KB Output is correct
4 Correct 108 ms 25720 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 25876 KB Output is correct
2 Correct 175 ms 25820 KB Output is correct
3 Correct 95 ms 25816 KB Output is correct
4 Correct 102 ms 25728 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 12032 KB Output is correct
2 Correct 12 ms 12004 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 2920 KB Output is correct
2 Correct 111 ms 3520 KB Output is correct
3 Correct 66 ms 3576 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 17504 KB Output is correct
2 Correct 221 ms 18316 KB Output is correct
3 Correct 95 ms 18296 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 24772 KB Output is correct
2 Correct 317 ms 25656 KB Output is correct
3 Correct 125 ms 25684 KB Output is correct