제출 #109249

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
109249		MetB	Pairs (IOI07_pairs)	C++14	100 / 100	448 ms	294016 KiB

pairs

#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;
	}
 
}

컴파일 시 표준 에러 (stderr) 메시지

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