oj.uz

Submission #355619

# Submission time Handle Problem Language Result Execution time Memory
355619 2021-01-22T21:03:42 Z ogibogi2004 Pairs (IOI07_pairs) C++14
30 / 100
 90 ms 9568 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int b,n,d,m;
void solve1()
{
	vector<int>v;
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		v.push_back(x);
	}
	sort(v.begin(),v.end());
	queue<int>q;
	long long ans=0;
	for(int 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<int>animals[200000];
int bit[200000];
void update(int idx,int val)
{
	idx++;
	for(;idx<200000;idx+=idx&(-idx))
	{
		bit[idx]+=val;
	}
}
int query(int idx)
{
	//cout<<idx<<endl;
	idx++;
	int ret=0;
	for(;idx>0;idx-=idx&(-idx))
	{
		ret+=bit[idx];
	}
	return ret;
}
ll query(int l,int r)
{
	return query(r)-query(l-1);
}
void solve2()
{
	vector<pair<int,int> >v;
	int min1=(int)1e9,min2=(int)1e9;
	for(int i=1;i<=n;i++)
	{
		int 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(int 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(int i=0;i<200000;i++)
	{
		//cout<<i<<endl;
		sort(animals[i].begin(),animals[i].end());
		if(i-d-1>=0)
		{
			for(auto a:animals[i-d])
			{
				update(a,-1);
			}
		}
		for(auto a:animals[i])
		{
			ans+=query(a-d,a+d);
			update(a,+1);
		}
	}
	cout<<ans<<endl;
}
int main()
{
	cin>>b>>n>>d>>m;
	if(b==1)solve1();
	if(b==2)solve2();
return 0;
}

Compilation message

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

Subtask #1
6.0 / 6.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

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

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 5736 KB Output is correct
2 Correct 50 ms 5988 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 5800 KB Output is correct
2 Correct 51 ms 5736 KB Output is correct
3 Correct 50 ms 5876 KB Output is correct

Subtask #6
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 5596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 7008 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 7392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 90 ms 9568 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 5120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4972 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4972 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4972 KB Output isn't correct
2 Halted 0 ms 0 KB -