oj.uz

Submission #109249

# Submission time Handle Problem Language Result Execution time Memory
109249 2019-05-05T21:34:23 Z MetB Pairs (IOI07_pairs) C++14
100 / 100
 448 ms 294016 KB 
#include <iostream>
#include <cstdlib>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include <bitset>
#include <queue>
#include <math.h>
#include <stack>
#include <vector>
#include <string.h>
#include <random>
 
typedef long long ll;
 
const ll MOD = 1e9 + 7, INF = 1e18;
 
using namespace std;
 
struct Fenwick1D
{
	vector <int> t;
	int n;
 
	void build (int v)
	{
		n = v;
		t.resize (n + 10);
	}
 
	void update (int x, int d)
	{
		for (;x <= n; x = (x | (x + 1)))
			t[x] += d;
	}
 
	int get (int r)
	{
		int sum = 0;
		for (;r >= 0; r = (r & (r + 1)) - 1)
			sum += t[r];
		return sum;
	}
 
	int get (int l, int r)
	{
		return get (r) - get (l - 1);
	}
} t1d;
 
struct Fenwick3D
{
	vector < vector < vector <int> > > t;
	int n;
 
	void build (int v)
	{
		n = v;
		t.resize (n + 1);
 
		for (int i = 0; i <= n; i++)
			t[i].resize (n + 1);

		for (int i = 0; i <= n; i++)
			for (int j = 0; j <= n; j++)
				t[i][j].resize (n + 1);
	}
 
	void update (int x, int y, int z, int d)
	{
		for (int i = x; i <= n; i = (i | (i + 1)))
			for (int j = y; j <= n; j = (j | (j + 1)))
				for (int k = z; k <= n; k = (k | (k + 1)))
				t[i][j][k] += d;
	}
 
	int get (int x, int y, int z)
	{
		int sum = 0;

		for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
			for (int j = y; j >= 0; j = (j & (j + 1)) - 1)
				for (int k = z; k >= 0; k = (k & (k + 1)) - 1)
					sum += t[i][j][k];
		return sum;
	}
 
	int get (int x2, int y2, int z2, int x1, int y1, int z1)
	{
		return get (x2, y2, z2) - get (x1 - 1, y2, z2) - get (x2, y1 - 1, z2) - get (x2, y2, z1 - 1) + 
				get (x1 - 1, y1 - 1, z2) + get (x1 - 1, y2, z1 - 1) + get (x2, y1 - 1, z1 - 1) - get (x1 - 1, y1 - 1, z1 - 1);
	}
} t3d;
 
int n, b, d, m, a[100000];
 
ll ans;

struct point
{
	int x, y, z, i;

	bool operator < (const point& b)
	{
		return i < b.i;
	}
};
 
int main ()
{
	cin >> b >> n >> d >> m;
 
	if (b == 1)
	{
		t1d.build (m);
 
		for (int i = 0; i < n; i++)
			scanf ("%d", &a[i]);
 
		sort (a, a + n);
 
		for (int i = 0; i < n; i++)
		{
			ans += t1d.get (a[i] - d, a[i]);
			t1d.update (a[i], 1);
		}
 
		cout << ans << endl;
	}
	else if (b == 2)
	{
		t1d.build (2 * m);
 
		vector < pair <int, int> > a (n);
 
		for (int i = 0; i < n; i++)
		{
			int x, y;
 
			scanf ("%d%d", &x, &y);
 
			a[i].first = x + y;
			a[i].second = m + x - y;
		}

		sort (a.begin(), a.end());

		int j = 0;
 
		for (int i = 0; i < n; i++)
		{
			while (a[i].first - a[j].first > d)
			{
				t1d.update (a[j].second, -1);
				j++;
			}

			ans += t1d.get (a[i].second - d, min (2 * m, a[i].second + d));

			t1d.update (a[i].second, 1);
		}

		cout << ans << endl;
	}
	else
	{
		t3d.build (3 * m);
 
		vector < point > a (n);
 
		for (int i = 0; i < n; i++)
		{
			int x, y, z;
 
			scanf ("%d%d%d", &x, &y, &z);
 
			a[i].x = x + y + z;
			a[i].y = m + x + y - z;
			a[i].z = m + x - y + z;
			a[i].i = x - y - z;
		}

		sort (a.begin(), a.end());

		int j = 0;
 
		for (int i = 0; i < n; i++)
		{
			while (a[i].i - a[j].i > d)
			{
				t3d.update (a[j].x, a[j].y, a[j].z, -1);
				j++;
			}

			ans += t3d.get (min (3 * m, a[i].x + d), min (3 * m, a[i].y + d), min (3 * m, a[i].z + d), 
				max (0, a[i].x - d), max (0, a[i].y - d), max (0, a[i].z - d));

			t3d.update (a[i].x, a[i].y, a[i].z, 1);
		}

		cout << ans << endl;
	}
 
}

Compilation message

pairs.cpp: In function 'int main()':
pairs.cpp:119:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf ("%d", &a[i]);
    ~~~~~~^~~~~~~~~~~~~
pairs.cpp:141:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf ("%d%d", &x, &y);
    ~~~~~~^~~~~~~~~~~~~~~~
pairs.cpp:176:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf ("%d%d%d", &x, &y, &z);
    ~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 294016 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 768 KB Output is correct
2 Correct 19 ms 640 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 274808 KB Output is correct
2 Correct 293 ms 274768 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 274828 KB Output is correct
2 Correct 245 ms 274680 KB Output is correct
3 Correct 254 ms 274720 KB Output is correct

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1152 KB Output is correct
2 Correct 46 ms 1168 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 1152 KB Output is correct
2 Correct 36 ms 1276 KB Output is correct
3 Correct 34 ms 1164 KB Output is correct
4 Correct 41 ms 1152 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 1708 KB Output is correct
2 Correct 40 ms 1664 KB Output is correct
3 Correct 53 ms 1712 KB Output is correct
4 Correct 40 ms 1784 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 47096 KB Output is correct
2 Correct 47 ms 47224 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 2688 KB Output is correct
2 Correct 59 ms 2660 KB Output is correct
3 Correct 64 ms 2688 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 27152 KB Output is correct
2 Correct 359 ms 27128 KB Output is correct
3 Correct 102 ms 27128 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 440 ms 49656 KB Output is correct
2 Correct 448 ms 49528 KB Output is correct
3 Correct 134 ms 49600 KB Output is correct