oj.uz

Submission #109186

# Submission time Handle Problem Language Result Execution time Memory
109186 2019-05-05T11:26:27 Z MetB Pairs (IOI07_pairs) C++14
30 / 100
 4000 ms 525312 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 + 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;
	}

}

Compilation message

pairs.cpp: In function 'int main()':
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.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 222 ms 293880 KB Output is correct

Subtask #3
6.0 / 6.0

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

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 274936 KB Output is correct
2 Correct 285 ms 275064 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 275096 KB Output is correct
2 Correct 278 ms 275064 KB Output is correct
3 Correct 258 ms 274936 KB Output is correct

Subtask #6
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 427 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4086 ms 1152 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4030 ms 4992 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 398 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

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

Subtask #11
0 / 10.0

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

Subtask #12
0 / 10.0

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

Subtask #13
0 / 10.0

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