제출 #1136985

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1136985		cowwycow	Pairs (IOI07_pairs)	C++20	100 / 100	1002 ms	104784 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;
}

const int N = 6e5 + 5, M = 3e5, G = 6e5, L = 1e5, R = 5e5;

vector<int> pos[N];
vector<int> BIT[N];

void fakeAdd(int u, int v, int x){
	for(u; u <= G; u += u&(-u)){
		pos[u].push_back(v);
	}
}

void fakeQuery(int u, int v){
	for(u; u > 0; u -= u&(-u)){
		pos[u].push_back(v);
	}
}

void fakeQueryrect(int x1, int y1, int x2, int y2){
	fakeQuery(x2, y2);
	fakeQuery(x1 - 1, y2);
	fakeQuery(x2, y1 - 1);
	fakeQuery(x1 - 1, y1 - 1);
}

void compress(){
	for(int i = 1; i <= G; i++){
		pos[i].push_back(0);
		sort(pos[i].begin(), pos[i].end());
		pos[i].erase(unique(pos[i].begin(), pos[i].end()), pos[i].end());
		BIT[i].assign(pos[i].size(), 0);
	}
}

void add(int u, int v, int x){
	for(int i = u; i <= G; i += i&(-i)){
		for(int j = lower_bound(pos[i].begin(), pos[i].end(), v) - pos[i].begin(); j < BIT[i].size(); j += j&(-j)){
			BIT[i][j] += x;
		}
	}
}

int query(int u, int v){
	int sum = 0;
	for(int i = u; i > 0; i -= i&(-i)){
		for(int j = lower_bound(pos[i].begin(), pos[i].end(), v) - pos[i].begin(); j > 0; j -= j&(-j)){
			sum += BIT[i][j];
		}
	}
	return sum;
}

int queryrect(int x1, int y1, int x2, int y2){
	return query(x2, y2) - query(x1 - 1, y2) - query(x2, y1 - 1) + query(x1 - 1, y1 - 1);
}

pll a[N];

void type2(){
	ll n, d, m;
	cin >> n >> d >> m;
	for(int i = 1; i <= n; i++){
		cin >> a[i].first >> a[i].second;
		int x = a[i].first + a[i].second + M, y = a[i].first - a[i].second + M;
		a[i].first = x, a[i].second = y;
		fakeAdd(x, y, 1);
	}
	for(int i = 1; i <= n; i++){
		int x1 = a[i].first - d, y1 = a[i].second - d, x2 = a[i].first + d, y2 = a[i].second + d;
		x1 = max(x1, L), y1 = max(y1, L), x2 = min(x2, R), y2 = min(y2, R);
		fakeQueryrect(x1, y1, x2, y2);
	}
	compress();

	for(int i = 1; i <= n; i++){
		add(a[i].first, a[i].second, 1);
	}
	ll ans = 0;
	for(int i = 1; i <= n; i++){
		int x1 = a[i].first - d, y1 = a[i].second - d, x2 = a[i].first + d, y2 = a[i].second + d;
		x1 = max(x1, L), y1 = max(y1, L), x2 = min(x2, R), y2 = min(y2, R);
		ans += queryrect(x1, y1, x2, y2);
	}
	ans = (ans - n) / 2;
	cout << ans;
}

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();
	}
}

컴파일 시 표준 에러 (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: 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