Submission #411685

#	Time	Username	Problem	Language	Result	Execution time	Memory
411685		Jasiekstrz	Pairs (IOI07_pairs)	C++17	37 / 100	65 ms	5680 KiB

pairs

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=1e5;
namespace d1
{
	int tab[N+10];
	long long solve()
	{
		int n,d,m;
		cin>>n>>d>>m;
		for(int i=1;i<=n;i++)
			cin>>tab[i];
		sort(tab+1,tab+n+1);
		long long ans=0;
		for(int i=1,j=1;i<=n;i++)
		{
			while(tab[i]-tab[j]>d)
				j++;
			ans+=i-j;
		}
		return ans;
	}
};
namespace d2
{
	const int P=27e4;
	struct Event
	{
		int x,y;
		int val;
		bool operator<(const Event &oth)
		{
			return x<oth.x;
		}
	};
	pair<int,int> tab[N+10];
	vector<Event> ev;
	int pot;
	int tree[2*P+10];
	void add(int x,int c)
	{
		for(x+=pot-1;x>0;x/=2)
			tree[x]+=c;
		return;
	}
	long long read(int l,int r)
	{
		l=max(1,l);r=min(pot,r);
		long long ans=0;
		for(l+=pot-1,r+=pot-1;l<=r;l/=2,r/=2)
		{
			if(l%2==1)
				ans+=tree[l++];
			if(r%2==0)
				ans+=tree[r--];
		}
		return ans;
	}
	long long solve()
	{
		int n,d,m;
		cin>>n>>d>>m;
		for(int i=1;i<=n;i++)
		{
			cin>>tab[i].fi>>tab[i].se;
			ev.push_back({tab[i].fi-tab[i].se,tab[i].fi+tab[i].se,1});
			ev.push_back({tab[i].fi-tab[i].se+d+1,tab[i].fi+tab[i].se,-1});
		}
		sort(ev.begin(),ev.end());
		for(pot=1;pot<2*m;pot++);
		long long ans=-n;
		for(int i=-m,j=0;i<=m;i++)
		{
			size_t it;
			for(it=j;it<ev.size() && ev[it].x==i;it++)
				add(ev[it].y,ev[it].val);
			for(it=j;it<ev.size() && ev[it].x==i;it++)
			{
				if(ev[it].val==1)
					ans+=read(ev[it].y-d,ev[it].y+d);
			}
			j=it;
		}
		return ans;
	}
};
namespace d3
{
	long long solve()
	{
		return 0;
	}
};
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int board_type;
	cin>>board_type;
	if(board_type==1)
		cout<<d1::solve();
	else if(board_type==2)
		cout<<d2::solve();
	else
		cout<<d3::solve();
	cout<<"\n";
	return 0;
}

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