제출 #1147126

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1147126		Tsagana	Pairs (IOI07_pairs)	C++20	100 / 100	25 ms	3248 KiB

pairs

#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define int long long
#define pii pair<int, int>
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second

using namespace std;

int B, N, D, M;

struct B1 {
	void solve(){
		vector<int> v(N);
		for (auto &i: v) cin >> i;
		sort(all(v));
		int p = 0, ans = 0;
		for (int i = 0; i < N; i++) {
			while (p < N && v[i] - v[p] > D) p++;
			ans += i - p;
		}
		cout << ans << '\n';
	}
} b1;

struct B2 {
	int bit[150010];

	void update(int x, int k){
		for (int i = x; i <= 2 * M; i += i & -i) bit[i] += k;
	}
	int query(int x) {
		int res = 0;
		for (int i = x; i >= 1; i-= i & -i) res += bit[i];
		return res;
	}

	void solve(){
		vector<pii> v(N);
		for (int i = 0; i < N; i++) {
			cin >> v[i].F >> v[i].S;
			v[i] = {v[i].F + v[i].S, v[i].F - v[i].S + M};
		}
		sort(all(v));
		int p = 0, ans = 0;
		for (int i = 0; i < N; i++) {
			while (p < N && v[i].F - v[p].F > D) update(v[p++].S, -1);
			int l = max(1LL, v[i].S - D), r = min(2 * M, v[i].S + D);
			ans += query(r) - query(l-1);
			update(v[i].S, 1);
		}
		cout << ans << '\n';
	}
} b2;

struct B3 {
	vector<pii> v[160];
	int cnt[160][160];

	void solve() {
		for (int i = 0; i < N; i++) {
			int x, y, z; cin >> x >> y >> z;
			v[x].pb({y + z, y - z + M});
		}
		int ans = 0;
		for (int i = 1; i <= M; i++) {
			for (int a = 1; a <= 2*M; a++)
			for (int b = 1; b <= 2*M; b++)
				cnt[a][b]=0;

			for (auto [x, y]: v[i]) cnt[x][y]++;

			for (int a = 1; a <= 2*M; a++)
			for (int b = 1; b <= 2*M; b++)
				cnt[a][b] += cnt[a-1][b] + cnt[a][b-1] - cnt[a-1][b-1];

			for (int j = i; j <= M; j++) {
				int d = D - (j - i);
				if (d < 0) continue ;
				int add = 0;
				for (auto [x, y]: v[j]) {
					int u = min(2*M, x + d), v = min(2*M, y + d);
					x = max(1LL, x - d); y = max(1LL, y - d);
					add += cnt[u][v] - cnt[x-1][v] - cnt[u][y-1] + cnt[x-1][y-1];
				}
				if (j == i) add = (add - v[i].size()) / 2;
				ans += add;
			}
		}
		cout << ans << '\n';
	}
} b3;

void solve () {
	cin >> B >> N >> D >> M;
	if (B == 1) b1.solve();
	else if (B == 2) b2.solve();
	else b3.solve();
}
signed main() {IOS solve(); return 0;}

• 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