oj.uz

Submission #109246

# Submission time Handle Problem Language Result Execution time Memory
109246 2019-05-05T19:46:47 Z MetB Pairs (IOI07_pairs) C++14
60 / 100
 293 ms 294004 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, 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)
	{
		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 b /= 0;
 
}

Compilation message

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

Subtask #3
6.0 / 6.0

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

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 275552 KB Output is correct
2 Correct 277 ms 275676 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 275704 KB Output is correct
2 Correct 272 ms 275556 KB Output is correct
3 Correct 251 ms 275592 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 1784 KB Output is correct
2 Correct 29 ms 1712 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 1920 KB Output is correct
2 Correct 33 ms 1948 KB Output is correct
3 Correct 46 ms 1912 KB Output is correct
4 Correct 32 ms 1920 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 2816 KB Output is correct
2 Correct 40 ms 2868 KB Output is correct
3 Correct 38 ms 2888 KB Output is correct
4 Correct 38 ms 2816 KB Output is correct

Subtask #10
0 / 10.0

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

Subtask #11
0 / 10.0

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

Subtask #12
0 / 10.0

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

Subtask #13
0 / 10.0

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