Submission #469423

#	Time	Username	Problem	Language	Result	Execution time	Memory
469423		flashmt	Pairs (IOI07_pairs)	C++17	100 / 100	281 ms	25460 KiB

pairs

#include <bits/stdc++.h>
#define fr(a,b,c) for (a=b;a<=c;a++)
using namespace std;

struct point { int x,y,z,t; };

struct BIT
{
	int size,f[150150];

	void update(int x,int v)
	{
		while (x<=size) f[x]+=v, x+=x&-x;
	}

   int get(int x)
	{
		int r=0;
		x=max(x,0); x=min(x,size);
		while (x) r+=f[x], x-=x&-x;
		return r;
	}
};

struct BIT_3D
{
	int size1,size2,size3,f[230][230][230];

	void update(int x,int y,int z,int v)
	{
		while (x<=size1)
		{
			int yy=y;
			while (yy<=size2)
			{
				int zz=z;
				while (zz<=size3) f[x][yy][zz]+=v, zz+=zz&-zz;
				yy+=yy&-yy;
			}
			x+=x&-x;
		}
	}

	int get(int x,int y,int z)
	{
		int r=0;
		x=max(x,0); x=min(x,size1);
		y=max(y,0); y=min(y,size2);
		z=max(z,0); z=min(z,size3);
		while (x)
		{
			int yy=y;
			while (yy)
			{
				int zz=z;
				while (zz) r+=f[x][yy][zz], zz-=zz&-zz;
				yy-=yy&-yy;
			}
			x-=x&-x;
		}
		return r;
	}
};

int type,n,m,d;
long long re;
vector < point > a;
BIT c;
BIT_3D e;

bool cmp(point i,point j)
{
	return i.x<j.x;
}

void work1()
{
	int i,j=0;
	point u;
	fr(i,1,n)	scanf("%d",&u.x),	a.push_back(u);
	sort(a.begin(),a.end(),cmp);
	fr(i,1,n-1)
	{
		while (a[j].x+d<a[i].x) j++;
		re+=i-j;
	}
}

void work2()
{
	int i,j=0,x,y;
	point u;
	c.size=m*2;
	fr(i,1,n)
	{
		scanf("%d%d",&x,&y);
		u.x=x-y; u.y=x+y;
		a.push_back(u);
	}
	sort(a.begin(),a.end(),cmp);
	c.update(a[0].y,1);
	fr(i,1,n-1)
	{
		while (a[j].x+d<a[i].x) c.update(a[j++].y,-1);
		re+=c.get(a[i].y+d)-c.get(a[i].y-d-1);
		c.update(a[i].y,1);
	}
}

int calc(int y,int yy,int z,int zz,int t,int tt)
{
	return e.get(y,z,t)-e.get(y,z,tt)-e.get(y,zz,t)-e.get(yy,z,t)+e.get(y,zz,tt)+e.get(yy,z,tt)+e.get(yy,zz,t)-e.get(yy,zz,tt);
}

void work3()
{
	int i,j=0,x,y,z,zz=1000,tt=1000;
	point u;
	fr(i,1,n)
	{
		scanf("%d%d%d",&x,&y,&z);
		u.x=x-y-z; u.y=x+y+z;
		u.z=x+y-z; u.t=x-y+z;
		zz=min(zz,u.z); tt=min(tt,u.t);
		a.push_back(u);
	}
	fr(i,0,n-1)
	{
		e.size1=max(e.size1,a[i].y);
		a[i].z-=(zz-1);	e.size2=max(e.size2,a[i].z);
		a[i].t-=(tt-1); e.size3=max(e.size3,a[i].t);
	}
	sort(a.begin(),a.end(),cmp);
	e.update(a[0].y,a[0].z,a[0].t,1);
	fr(i,1,n-1)
	{
		while (a[j].x+d<a[i].x) e.update(a[j].y,a[j].z,a[j].t,-1), j++;
		re+=calc(a[i].y+d,a[i].y-d-1,a[i].z+d,a[i].z-d-1,a[i].t+d,a[i].t-d-1);
		e.update(a[i].y,a[i].z,a[i].t,1);
	}
}

int main()
{
	cin >> type >> n >> d >> m;
	if (type==1) work1();
	else
		if (type==2) work2();
		else work3();
	cout << re << endl;
	return 0;
}

Compilation message (stderr)

pairs.cpp: In function 'void work1()':
pairs.cpp:80:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |  fr(i,1,n) scanf("%d",&u.x), a.push_back(u);
      |            ~~~~~^~~~~~~~~~~
pairs.cpp: In function 'void work2()':
pairs.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |   scanf("%d%d",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~
pairs.cpp: In function 'void work3()':
pairs.cpp:121:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |   scanf("%d%d%d",&x,&y,&z);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~

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