oj.uz

Submission #152933

# Submission time Handle Problem Language Result Execution time Memory
152933 2019-09-10T14:25:25 Z luciocf Pairs (IOI07_pairs) C++14
60 / 100
 77 ms 5492 KB 
#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

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.0 / 6.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

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

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1656 KB Output is correct
2 Correct 28 ms 1612 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1528 KB Output is correct
2 Correct 28 ms 1620 KB Output is correct
3 Correct 27 ms 1576 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3420 KB Output is correct
2 Correct 6 ms 3580 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 4840 KB Output is correct
2 Correct 50 ms 4828 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 4620 KB Output is correct
2 Correct 62 ms 5040 KB Output is correct
3 Correct 65 ms 4984 KB Output is correct
4 Correct 62 ms 4952 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 5336 KB Output is correct
2 Correct 68 ms 5492 KB Output is correct
3 Correct 68 ms 5368 KB Output is correct
4 Correct 66 ms 5368 KB Output is correct

Subtask #10
0 / 10.0

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

Subtask #11
0 / 10.0

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

Subtask #12
0 / 10.0

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

Subtask #13
0 / 10.0

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