Submission #71496

#	Time	Username	Problem	Language	Result	Execution time	Memory
71496		RezwanArefin01	Pairs (IOI07_pairs)	C++17	100 / 100	496 ms	78600 KiB

pairs

#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 (stderr)

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 / 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