제출 #109187

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
109187		MetB	Pairs (IOI07_pairs)	C++14	30 / 100	4088 ms	525312 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 + 1);
	}

	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, row2d, col2d;

struct Fenwick2D
{
	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);
	}

	void update (int x, int y, int d)
	{
		for (;x <= n; x = (x | (x + 1)))
			for (; y <= n; y = (y | (y + 1)))
				t[x][y] += d;
	}

	void print ()
	{
		for (int i = 0; i <= n; i++)
		{
			for (int j = 0; j <= n; j++)
				cout << t[i][j];
			cout << endl;
		}
	}

	int get (int r1, int r2)
	{
		int sum = 0;
		for (;r1 >= 0; r1 = (r1 & (r1 + 1)) - 1)
			for (;r2 >= 0; r2 = (r2 & (r2 + 1)) - 1)
				sum += t[r1][r2];
		return sum;
	}

	int get (int x2, int y2, int x1, int y1)
	{
		return get (x2, y2) - get (x1 - 1, y2) - get (x2, y1 - 1) + get (x1 - 1, y1 - 1);
	}
} t2d;

int n, b, d, m, a[100000];

ll ans;

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)
	{
		t2d.build (m);
		row2d.build (m);
		col2d.build (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 = x - y;

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

		for (int i = 0; i < n; i++)
		{
			ans += t2d.get (min (m, a[i].first + d), min (m, a[i].second + d), a[i].first - d, a[i].second - d);
			t2d.print ();
		}

		cout << ans / 2 << endl;
	}
	else b /= 0;

}

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

pairs.cpp: In function 'int main()':
pairs.cpp:151:9: warning: division by zero [-Wdiv-by-zero]
  else b /= 0;
       ~~^~~~
pairs.cpp:111:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf ("%d", &a[i]);
    ~~~~~~^~~~~~~~~~~~~
pairs.cpp:135:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf ("%d%d", &x, &y);
    ~~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 6 / 6
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 6 / 6
• Subtask 6: 0 / 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