oj.uz

Submission #71496

# Submission time Handle Problem Language Result Execution time Memory
71496 2018-08-24T23:13:01 Z RezwanArefin01 Pairs (IOI07_pairs) C++17
100 / 100
 496 ms 78600 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii; 

const int N = 1e5 + 10;
int x[N], y[N], z[N]; 
int b, n, d, m; 


int main(int argc, char const *argv[]) {
	scanf("%d %d %d %d", &b, &n, &d, &m); 
	if(b == 1) { 
		for(int i = 0; i < n; i++) 
			scanf("%d", &x[i]);
		sort(x, x + n);

		int l = 0, r = 0; 
		ll ans = 0; 

		while(r < n) {
			while(l < r && x[r] - x[l] > d) l++;
			ans += r - l; r++;
		} 
		printf("%lld\n", ans);
	} else if(b == 2) {
		vector<ii> v;
		for(int i = 0; i < n; i++) {
			scanf("%d %d", &x[i], &y[i]); 
			v.emplace_back(x[i] + y[i], x[i] - y[i] + m + 1);
		} 
		sort(v.begin(), v.end()); 

		m *= 3; 
		vector<int> BIT(m, 0); 

		auto update = [&BIT](int x, int v) {
			for(; x < m; x += x & -x) 
				BIT[x] += v;
		};

		auto query = [&BIT](int x) {
			int ret = 0;
			for(; x > 0; x -= x & -x) 
				ret += BIT[x]; 
			return ret; 
		};

		int l = 0, r = 0; ll ans = 0; 
		while(r < n) {
			while(l < n && v[r].first - v[l].first > d) {
				update(v[l].second, -1);
				l++;
			}
			ans += query(min(m - 1, v[r].second + d)) - 
				   query(max(0, v[r].second - d - 1));

			update(v[r].second, 1); 
			r++;
		}
		printf("%lld\n", ans);
	} else {
		vector<pair<ii, ii> > v;
		for(int i = 0; i < n; i++) {
			scanf("%d %d %d", &x[i], &y[i], &z[i]); 
			v.push_back({{x[i] + y[i] + z[i], x[i] + y[i] - z[i] + m + 1}, 
						   {x[i] - y[i] + z[i] + m + 1, 
						   x[i] - y[i] - z[i] + m + m + 2}});
		} 
		sort(v.begin(), v.end()); 
		m += 3; 
		vector<int> BIT(13824000, 0);
		auto update = [&BIT](int i, int j, int k, int v) {
			for(int x = i; x < 3 * m; x += x & -x) 
				for(int y = j; y < 3 * m; y += y & -y) 
					for(int z = k; z < 3 * m; z += z & -z) 
						BIT[x * 3 * m * 3 * m + y * 3 * m + z] += v; 
		};

		auto query = [&BIT](int i, int j, int k) {
			int ret = 0;
			for(int x = i; x > 0; x -= x & -x) 
				for(int y = j; y > 0; y -= y & -y) 
					for(int z = k; z > 0; z -= z & -z) 
						ret += BIT[x * 3 * m * 3 * m + y * 3 * m + z]; 
			return ret; 
		};
		auto get = [&query](int x1, int y1, int z1, int x2, int y2, int z2) {
			x1--, y1--, z1--;
			return query( x2, y2, z2 ) 
         			- query( x1, y2, z2 ) - query( x2, y1, z2 ) - query( x2, y2, z1 )
         			+ query( x1, y1, z2 ) + query( x1, y2, z1 ) + query( x2, y1, z1 )
					- query( x1, y1, z1 );
		};

		int l = 0, r = 0; ll ans = 0; 
		while(r < n) {
			while(l < n && v[r].first.first - v[l].first.first > d) {
				update(v[l].first.second, v[l].second.first, v[l].second.second, -1);
				l++;
			}
			int a = v[r].first.second, b = v[r].second.first, c = v[r].second.second;
			ans += get(max(1, a - d), max(1, b - d), max(1, c - d), min(3 * m, a + d), min(3 * m, b + d), min(3 * m, c + d));

			update(v[r].first.second, v[r].second.first, v[r].second.second, 1);
			r++;
		}
		printf("%lld\n", ans);
	}
}

Compilation message

pairs.cpp: In function 'int main(int, const char**)':
pairs.cpp:13:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d %d", &b, &n, &d, &m); 
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp:16:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &x[i]);
    ~~~~~^~~~~~~~~~~~~
pairs.cpp:30:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &x[i], &y[i]); 
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp:66:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d %d", &x[i], &y[i], &z[i]); 
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1368 KB Output is correct
2 Correct 27 ms 1896 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 2632 KB Output is correct
2 Correct 32 ms 3616 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 4516 KB Output is correct
2 Correct 34 ms 5252 KB Output is correct
3 Correct 40 ms 6272 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6808 KB Output is correct
2 Correct 4 ms 6820 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 8252 KB Output is correct
2 Correct 36 ms 8676 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 9504 KB Output is correct
2 Correct 49 ms 10272 KB Output is correct
3 Correct 44 ms 11032 KB Output is correct
4 Correct 43 ms 11792 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 13828 KB Output is correct
2 Correct 49 ms 14828 KB Output is correct
3 Correct 50 ms 15992 KB Output is correct
4 Correct 74 ms 17188 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 68820 KB Output is correct
2 Correct 54 ms 68832 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 72280 KB Output is correct
2 Correct 132 ms 72868 KB Output is correct
3 Correct 157 ms 73552 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 74384 KB Output is correct
2 Correct 376 ms 75100 KB Output is correct
3 Correct 177 ms 75936 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 496 ms 76768 KB Output is correct
2 Correct 488 ms 77736 KB Output is correct
3 Correct 192 ms 78600 KB Output is correct