oj.uz

Submission #469423

# Submission time Handle Problem Language Result Execution time Memory
469423 2021-09-01T00:43:50 Z flashmt Pairs (IOI07_pairs) C++17
100 / 100
 281 ms 25460 KB 
#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

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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 300 KB Output is correct

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 2880 KB Output is correct
2 Correct 21 ms 2860 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3148 KB Output is correct
2 Correct 29 ms 3184 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3168 KB Output is correct
2 Correct 27 ms 3136 KB Output is correct
3 Correct 27 ms 3136 KB Output is correct

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 3008 KB Output is correct
2 Correct 30 ms 3008 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 3172 KB Output is correct
2 Correct 37 ms 3136 KB Output is correct
3 Correct 42 ms 3252 KB Output is correct
4 Correct 35 ms 3024 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 3584 KB Output is correct
2 Correct 44 ms 3640 KB Output is correct
3 Correct 46 ms 3668 KB Output is correct
4 Correct 41 ms 3656 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 11432 KB Output is correct
2 Correct 6 ms 11468 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 3116 KB Output is correct
2 Correct 80 ms 3196 KB Output is correct
3 Correct 44 ms 2996 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 17536 KB Output is correct
2 Correct 235 ms 17616 KB Output is correct
3 Correct 80 ms 17584 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 25460 KB Output is correct
2 Correct 246 ms 25392 KB Output is correct
3 Correct 103 ms 25400 KB Output is correct