Submission #1136121

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136121		cowwycow	Pairs (IOI07_pairs)	C++20	70 / 100	273 ms	49084 KiB

pairs

#include <bits/stdc++.h>
using namespace std;
#define name "aaaaaa"
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using ppii = pair<ll, pii>;
using pll = pair<ll, ll>;
using ull = unsigned long long;

void file(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	if(fopen(name".inp", "r")) {
		freopen(name".inp", "r", stdin);
		freopen(name".out", "w", stdout);
	}
}

void type1(){
	int n, k;
	cin >> n >> k;
	int m; cin >> m;
	vector<int> v;
	for(int i = 1; i <= n; i++){
		int x; cin >> x;
		v.push_back(x);
	}
	sort(v.begin(), v.end());
	ll ans = 0;
	for(int i = 0; i < v.size(); i++){
		int pos = upper_bound(v.begin(), v.end(), v[i] + k) - v.begin() - 1;
		ans += pos - i;
	}
	cout << ans;
}

void type2(){

}

const int M3 = 230;

int ct[M3][M3][M3];

vector<pair<int, pii>> v;

int rect(int layer, int x1, int y1, int x2, int y2){
	x1 = max(x1, 1);
	x2 = min(x2, M3 - 1);
	y1 = max(y1, 1);
	y2 = min(y2, M3 - 1);
	return ct[layer][x2][y2] - ct[layer][x1 - 1][y2] - ct[layer][x2][y1 - 1] + ct[layer][x1 - 1][y1 - 1];
}

void type3(){
	int n, d, m;
	cin >> n >> d >> m;
	d = min(d, m * 3 - 1);
	for(int i = 1; i <= n; i++){
		int x, y, z;
		cin >> x >> y >> z;
		int y2 = y + z, z2 = y - z;
		y2 += 76, z2 += 76;
		ct[x][y2][z2]++;
		v.push_back({x, {y2, z2}});
	}
	for(int i = 1; i < M3; i++){
		for(int j = 1; j < M3; j++){
			for(int k = 1; k < M3; k++){
				ct[i][j][k] += ct[i][j - 1][k] + ct[i][j][k - 1] - ct[i][j - 1][k - 1];
			}
		}
	}
	ll ans = 0;
	for(auto i : v){
		int x = i.first, y = i.second.first, z = i.second.second;
		for(int j = d; j >= 0; j--){
			int layer = x - (d - j);
			if(layer < 0) break;
			int x1 = y - j, y1 = z - j, x2 = y + j, y2 = z + j;
			ans += rect(layer, x1, y1, x2, y2);
		}
		for(int j = d - 1; j >= 0; j--){
			int layer = x + (d - j);
			if(layer >= M3) break;
			int x1 = y - j, y1 = z - j, x2 = y + j, y2 = z + j;
			ans += rect(layer, x1, y1, x2, y2);
		}
	}
	ans = (ans - n) / 2;
	cout << ans;
}

void solve (){
	int b; cin >> b;
	if(b == 1){
		type1();
	}else if(b == 2){
		type2();
	}else{
		type3();
	}
}

int main(){
	file();
	int test = 1;
	//cin >> test;
	while(test--){
		solve();
	}
}

Compilation message (stderr)

pairs.cpp: In function 'void file()':
pairs.cpp:14:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |                 freopen(name".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp:15:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |                 freopen(name".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• 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: 10 / 10
• Subtask 11: 10 / 10
• Subtask 12: 10 / 10
• Subtask 13: 10 / 10