Submission #152933

#	Time	Username	Problem	Language	Result	Execution time	Memory
152933		luciocf	Pairs (IOI07_pairs)	C++14	60 / 100	77 ms	5492 KiB

pairs

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int maxn = 4e5+10;
const int add = 2e5+10;

pii a[maxn];

int bit[2][maxn];

void upd(int x, int v, int q)
{
	if (!x) return;

	for (; x < maxn; x += (x&-x))
		bit[q][x] += v;
}

int soma(int x, int q)
{
	int ans = 0;
	for (; x > 0; x -= (x&-x))
		ans += bit[q][x];
	return ans;
}

long long solve_1(void)
{
	int n, d, m;
	scanf("%d %d %d", &n, &d, &m);

	int x[n+1];

	for (int i = 1; i <= n; i++)
		scanf("%d", &x[i]);

	sort(x+1, x+n+1);

	long long ans = 0;

	int l = 1, r = 2;
	while (l <= n && r <= n)
	{
		if (l != r && x[r]-x[l] <= d)
			ans += 1ll*(r-l);

		if (x[r]-x[l] <= d) r++;
		else l++;
	}

	return ans;
}

long long solve_2(void)
{
	int n, D, m;
	scanf("%d %d %d", &n, &D, &m);

	for (int i = 1; i <= n; i++)
		scanf("%d %d", &a[i].first, &a[i].second);

	sort(a+1, a+n+1);

	long long ans = 0;
	int ptr = 1;

	upd(a[1].first+a[1].second+add, 1, 0);
	upd(a[1].second+add, 1, 1);

	for (int i = 2; i <= n; i++)
	{
		while (ptr < i && a[i].first-a[ptr].first > D)
		{
			upd(a[ptr].first+a[ptr].second+add, -1, 0);
			upd(a[ptr].second+add, -1, 1);

			ptr++;
		}

		if (i != ptr)
		{
			ans += 1ll*(soma(maxn-1, 0)-soma(a[i].first+a[i].second-D-1+add, 0));
			ans -= 1ll*(soma(maxn-1, 1)-soma(a[i].second+add, 1));
		}

		upd(a[i].first+a[i].second+add, 1, 0);
		upd(a[i].second+add, 1, 1);
	}

	memset(bit, 0, sizeof bit);

	ptr = 1;

	upd(a[1].first-a[1].second+add, 1, 0);
	upd(a[1].second+add, 1, 1);

	for (int i = 2; i <= n; i++)
	{
		while (ptr < i && a[i].first-a[ptr].first > D)
		{
			upd(a[ptr].first-a[ptr].second+add, -1, 0);
			upd(a[ptr].second+add, -1, 1);

			ptr++;
		}

		if (i != ptr)
		{
			ans += 1ll*(soma(maxn-1, 0)-soma(a[i].first-a[i].second-D-1+add, 0));
			ans -= 1ll*soma(a[i].second+add, 1);
		}

		upd(a[i].first-a[i].second+add, 1, 0);
		upd(a[i].second+add, 1, 1);
	}

	return ans;
}

int main(void)
{
	int b;
	scanf("%d", &b);

	if (b == 1) printf("%lld\n", solve_1());
	else printf("%lld\n", solve_2());
}

Compilation message (stderr)

pairs.cpp: In function 'long long int solve_1()':
pairs.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &d, &m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp:38:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x[i]);
   ~~~~~^~~~~~~~~~~~~
pairs.cpp: In function 'long long int solve_2()':
pairs.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &D, &m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &a[i].first, &a[i].second);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp: In function 'int main()':
pairs.cpp:126:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &b);
  ~~~~~^~~~~~~~~~

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