oj.uz

Submission #904392

# Submission time Handle Problem Language Result Execution time Memory
904392 2024-01-12T04:48:41 Z Faisal_Saqib Pairs (IOI07_pairs) C++17
92 / 100
 1805 ms 524288 KB 
#pragma optimze("Ofast")
#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>
using namespace std;
// #define endl '\n'
const int N=76;
int pre[N][N][N];
// bool have1[N];
bitset<100> have1;
int have3[N][N][N];
int main()
{
	  ios::sync_with_stdio(false);
	  cout.tie(NULL);
	  cin.tie(NULL);
	int b,m;
	cin>>b;
	if(b==1)
	{
		int n,d;
		cin>>n>>d>>m;
		vector<int> a;
		for(int i=0;i<n;i++)
		{
			int x;
			cin>>x;
			a.push_back(x);
		}
		long long cnt=0;
		sort(begin(a),end(a));
		int i=0;
		for(int j=0;j<n;j++)
		{
			while(i<n and a[i]<(a[j]-d))
			{
				i++;
			}
			cnt+=(j-i);
		}
		cout<<cnt<<'\n';
	}
	else if(b==2)
	{
		// exit(-1);
		int n,d;
		cin>>n>>d>>m;
		long long ap1=n;
		ap1*=ap1;
		long long kp=(2e8);
		if(ap1<=kp)
		{
			vector<pair<int,int>> a;
			for(int i=0;i<n;i++)
			{
				int x,y;
				cin>>x>>y;
				a.push_back({x,y});
			}
			long long cnt=0;
			for(int i=0;i<n;i++)
			{
				for(int k=i+1;k<n;k++)
				{
					if((abs(a[i].first-a[k].first)+abs(a[i].second-a[k].second))<=d)
					{
						cnt++;
					}
				}
			}
			cout<<cnt<<'\n';
			exit(0);
		}
		vector<pair<int,int>> a;
		vector<vector<int>> pre1;
		vector<int> ap;
		// for(int i=0;i<=m;i++)
		// 	ap.push_back(0);
		for(int j=0;j<=m;j++)
			pre1.push_back(ap);
		for(int i=0;i<n;i++)
		{
			int x,y;
			cin>>x>>y;
			a.push_back({x,y});
			while(pre1[x].size()<=m)
			{
				pre1[x].push_back(0);
			}
			while(y<=m)
			{
				pre1[x][y]++;
				y++;
			}
		}
		long long cnt=0;
		for(int i=0;i<n;i++)
		{
			int x=a[i].first;
			int y=a[i].second;
			for(int dx=0;dx<=d and dx<=(m-1);dx++)
			{
				int dy=d-dx;
				if((x+dx)<=m and pre1[x+dx].size()>0)
				{
					cnt+=(pre1[(x+dx)][min(m,y+dy)]-pre1[x+dx][max(0,y-dy-1)])-(dx==0);
				}
				if((x-dx)>0 and dx!=0  and pre1[x-dx].size()>0)
				{
					cnt+=(pre1[(x-dx)][min(m,y+dy)]-pre1[x-dx][max(0,y-dy-1)]);
				}
			}
			// cout<<"For "<<i<<' '<<cnt<<endl;
		}
		cout<<cnt/2<<'\n';
	}
	else
	{
		int n,d;
		cin>>n>>d>>m;
		long long ap1=n;
		ap1*=ap1;
		long long kp=(2e8);
		if(ap1<=kp)
		{
			vector<vector<int>> a;
			for(int i=0;i<n;i++)
			{
				int x,y,z;
				cin>>x>>y>>z;
				a.push_back({x,y,z});
			}
			long long cnt=0;
			for(int i=0;i<n;i++)
			{
				for(int j=i+1;j<n;j++)
				{
					if((abs(a[i][0]-a[j][0])+abs(a[i][1]-a[j][1])+abs(a[i][2]-a[j][2]))<=d)
					{
						cnt++;
					}
				}
			}
			cout<<cnt<<'\n';
			exit(0);
		}
		vector<pair<int,pair<int,int>>> a;
		for(int i=0;i<n;i++)
		{
			int x,y,z;
			cin>>x>>y>>z;
			a.push_back({x,{y,z}});
			have1[x]=1;
			have3[x][y][z]++;
			while(z<=m)
			{
				pre[x][y][z]++;
				z++;
			}
		}
		long long cnt=0;
		d=min(d,(m-1)*b);
		sort(begin(a),end(a));
		a.resize(unique(begin(a),end(a))-begin(a));
		for(int i=0;i<a.size();i++)
		{
			int x=a[i].first,y=a[i].second.first,z=a[i].second.second;
			int p=0;
			for(int dx=0;dx<=(d) and dx<=(m-1);dx++)
			{
				if((x+dx>m or !have1[x+dx]) and ((x-dx)<=0 or !have1[x-dx]))
					continue;
				for(int dy=0;dy<=(m-1) and dy<=d and (dy+dx)<=d and (dy+dx)<=(2*(m-1));dy++)
				{
					int dz=d-(dy+dx);
					if((x+dx)<=m)
					{
						if((y+dy)<=m)
						{
							p+=(pre[x+dx][y+dy][min(m,z+dz)]-pre[x+dx][y+dy][max(0,z-dz-1)])-((dx==0) and (dy==0));
						}
						if((y-dy)>0 and (dy!=0))
						{
							p+=(pre[x+dx][y-dy][min(m,z+dz)]-pre[x+dx][y-dy][max(0,z-dz-1)])-((dx==0) and (dy==0));
						}
					}
					if((x-dx)>0 and (dx!=0))
					{
						if((y+dy)<=m)
						{
							p+=(pre[x-dx][y+dy][min(m,z+dz)]-pre[x-dx][y+dy][max(0,z-dz-1)])-((dx==0) and (dy==0));
						}
						if((y-dy)>0 and (dy!=0))
						{
							p+=(pre[x-dx][y-dy][min(m,z+dz)]-pre[x-dx][y-dy][max(0,z-dz-1)])-((dx==0) and (dy==0));
						}
					}
				}
			}
			cnt+=p*have3[x][y][z];
		}
		cout<<cnt/2<<'\n';
	}
	return 0;
}

Compilation message

pairs.cpp:1: warning: ignoring '#pragma optimze ' [-Wunknown-pragmas]
    1 | #pragma optimze("Ofast")
      | 
pairs.cpp: In function 'int main()':
pairs.cpp:87:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   87 |    while(pre1[x].size()<=m)
      |          ~~~~~~~~~~~~~~^~~
pairs.cpp:166:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |   for(int i=0;i<a.size();i++)
      |               ~^~~~~~~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

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

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1760 KB Output is correct
2 Correct 15 ms 1864 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1760 KB Output is correct
2 Correct 15 ms 2012 KB Output is correct
3 Correct 17 ms 1760 KB Output is correct

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1996 KB Output is correct
2 Correct 58 ms 2268 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 6348 KB Output is correct
2 Correct 484 ms 6256 KB Output is correct
3 Correct 414 ms 5836 KB Output is correct
4 Correct 497 ms 6344 KB Output is correct

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 1402 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 3 ms 448 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 4820 KB Output is correct
2 Correct 23 ms 4820 KB Output is correct
3 Correct 23 ms 4820 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 5844 KB Output is correct
2 Correct 605 ms 5844 KB Output is correct
3 Correct 931 ms 5844 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 417 ms 6100 KB Output is correct
2 Correct 1422 ms 6100 KB Output is correct
3 Correct 1805 ms 6352 KB Output is correct