oj.uz

Submission #355633

# Submission time Handle Problem Language Result Execution time Memory
355633 2021-01-22T22:07:08 Z ogibogi2004 Pairs (IOI07_pairs) C++14
100 / 100
 503 ms 88300 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll b,n,d,m;
void solve1()
{
	vector<ll>v;
	for(ll i=1;i<=n;i++)
	{
		ll x;
		cin>>x;
		v.push_back(x);
	}
	sort(v.begin(),v.end());
	queue<ll>q;
	long long ans=0;
	for(ll i=0;i<v.size();i++)
	{
		q.push(v[i]);
		while(v[i]-q.front()>d)
		{
			q.pop();
		}
		ans+=q.size()-1;
	}
	cout<<ans<<endl;
}
vector<ll>animals[500000];
ll bit[500000];
void update(ll idx,ll val)
{
	idx++;
	for(;idx<500000;idx+=idx&(-idx))
	{
		bit[idx]+=val;
	}
}
ll query(ll idx)
{
	//cout<<idx<<endl;
	idx++;
	ll ret=0;
	for(;idx>0;idx-=idx&(-idx))
	{
		ret+=bit[idx];
	}
	return ret;
}
ll query(ll l,ll r)
{
	return query(r)-query(l-1);
}
void solve2()
{
	vector<pair<ll,ll> >v;
	ll min1=(ll)1e9,min2=(ll)1e9;
	for(ll i=1;i<=n;i++)
	{
		ll x,y;
		cin>>x>>y;
		v.push_back({x-y,x+y});
		min1=min(min1,v.back().first);
		min2=min(min2,v.back().second);
	}
	for(ll i=0;i<v.size();i++)
	{
		v[i].first-=min1;
		v[i].second-=min2;
	}
	for(auto xd:v)
	{
		animals[xd.first].push_back(xd.second);
	}
	ll ans=0;
	for(ll i=0;i<500000;i++)
	{
		//cout<<i<<endl;
		sort(animals[i].begin(),animals[i].end());
		if(i-d-1>=0)
		{
			for(auto a:animals[i-d-1])
			{
				update(a,-1);
			}
		}
		for(auto a:animals[i])
		{
			ans+=query(a-d,a+d);
			update(a,+1);
		}
	}
	cout<<ans<<endl;
}
ll bit3[400][400][400];
void update3(ll idx1,ll idx2,ll idx3,ll val)
{
	idx1++;
	idx2++;
	idx3++;
	for(ll i1=idx1;i1<400;i1+=i1&(-i1))
	for(ll i2=idx2;i2<400;i2+=i2&(-i2))
	for(ll i3=idx3;i3<400;i3+=i3&(-i3))
	{
		bit3[i1][i2][i3]+=val;
	}
}
ll query3(ll idx1,ll idx2,ll idx3)
{
	idx1++;
	idx2++;
	idx3++;
	if(idx1>=400)idx1=399;
	if(idx2>=400)idx2=399;
	if(idx3>=400)idx3=399;
	ll ans=0;
	for(ll i1=idx1;i1>0;i1-=i1&(-i1))
	for(ll i2=idx2;i2>0;i2-=i2&(-i2))
	for(ll i3=idx3;i3>0;i3-=i3&(-i3))
	{
		ans+=bit3[i1][i2][i3];
	}
	return ans;
}
ll query3(ll x1,ll y1,ll z1,ll x2,ll y2,ll z2)
{
	return query3(x2,y2,z2)-query3(x1-1,y2,z2)-query3(x2,y1-1,z2)-query3(x2,y2,z1-1)+query3(x2,y1-1,z1-1)+query3(x1-1,y2,z1-1)+query3(x1-1,y1-1,z2)-query3(x1-1,y1-1,z1-1);
}
struct point
{
	ll x,y,z;
	bool operator<(point const& other)const
	{
		return make_pair(x,make_pair(y,z))<make_pair(other.x,make_pair(other.y,other.z));
	}
};
vector<point>ivan[400];
void solve3()
{
	ll min1,min2,min3=(ll)1e9;
	min1=min3;min2=min3;
	for(ll i=1;i<=n;i++)
	{
		ll a,b,c;
		cin>>a>>b>>c;
		ivan[a+b+c].push_back({a+b-c,a-b+c,a-b-c});
		min1=min(min1,ivan[a+b+c].back().x);
		min2=min(min2,ivan[a+b+c].back().y);
		min3=min(min3,ivan[a+b+c].back().z);
	}
	for(ll i=0;i<400;i++)
	{
		for(ll j=0;j<ivan[i].size();j++)
		{
			ivan[i][j].x-=min1;
			ivan[i][j].y-=min2;
			ivan[i][j].z-=min3;
		}
	}
	ll ans=0;
	for(ll i=0;i<400;i++)
	{
		sort(ivan[i].begin(),ivan[i].end());
		if(i-d-1>=0)
		{
			for(auto a:ivan[i-d-1])
			{
				update3(a.x,a.y,a.z,-1);
			}
		}
		for(auto a:ivan[i])
		{
			//cout<<i<<" "<<a.x<<" "<<a.z<<" "<<a.y<<endl;
			ans+=query3(a.x-d,a.y-d,a.z-d,a.x+d,a.y+d,a.z+d);
			update3(a.x,a.y,a.z,+1);
		}
	}
	cout<<ans<<endl;
}
int main()
{
	cin>>b>>n>>d>>m;
	if(b==1)solve1();
	if(b==2)solve2();
	if(b==3)solve3();
return 0;
}

Compilation message

pairs.cpp: In function 'void solve1()':
pairs.cpp:17:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |  for(ll i=0;i<v.size();i++)
      |             ~^~~~~~~~~
pairs.cpp: In function 'void solve2()':
pairs.cpp:65:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |  for(ll i=0;i<v.size();i++)
      |             ~^~~~~~~~~
pairs.cpp: In function 'void solve3()':
pairs.cpp:152:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |   for(ll j=0;j<ivan[i].size();j++)
      |              ~^~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12032 KB Output is correct
2 Correct 8 ms 12012 KB Output is correct

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 13284 KB Output is correct
2 Correct 38 ms 13536 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 13284 KB Output is correct
2 Correct 56 ms 13664 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 13284 KB Output is correct
2 Correct 58 ms 13284 KB Output is correct
3 Correct 56 ms 13304 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 13420 KB Output is correct
2 Correct 13 ms 13292 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 14940 KB Output is correct
2 Correct 65 ms 14940 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 15200 KB Output is correct
2 Correct 79 ms 15224 KB Output is correct
3 Correct 72 ms 15068 KB Output is correct
4 Correct 78 ms 15244 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 16988 KB Output is correct
2 Correct 108 ms 16988 KB Output is correct
3 Correct 85 ms 16092 KB Output is correct
4 Correct 98 ms 16220 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 37356 KB Output is correct
2 Correct 27 ms 37868 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 18028 KB Output is correct
2 Correct 190 ms 17900 KB Output is correct
3 Correct 178 ms 17900 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 384 ms 63852 KB Output is correct
2 Correct 360 ms 63852 KB Output is correct
3 Correct 233 ms 64108 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 503 ms 87020 KB Output is correct
2 Correct 448 ms 87944 KB Output is correct
3 Correct 297 ms 88300 KB Output is correct