제출 #1177312

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1177312		sano	Pairs (IOI07_pairs)	C++20	60 / 100	231 ms	139192 KiB

pairs

#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#include <cassert>

#define shit short int
#define ll long long
//#define int ll
#define For(i, n) for(int i = 0; i < (int)n; i++)
#define ffor(i, a, n) for(int i = (int)a; i < (int)n; i++)
#define rfor(i, n) for(int i = (int)n; i >= (int)0; i--)
#define rffor(i, a, n) for(int i = (int)n; i >= (int)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<int, int>
#define NEK 2000000000
#define mod 1000000007
#define mod2 1000000009
#define rsz resize 
#define prv1 43
#define prv2 47
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define all(x) (x).begin(), (x).end()
#define sig 0.0000001

using namespace std;

class intervalac2d {
	int n, m;
	vec<vec<int>> bit;

public:
	intervalac2d(int vel1, int vel2) {
		n = vel1, m = vel2;
		bit.resize(n + 1, vec<int>(m + 1, 0));
		return;
	}
	void zmen(int a, int b, int k) {
		for (int i = a; i <= n; i += i & -i) {
			for (int j = b; j <= m; j += j & -j) {
				bit[i][j] += k;
			}
		}
		return;
	}
	 
	int prefix(int a, int b) {
		int odp = 0;
		for (int i = a; i > 0; i -= i & -i) {
			for (int j = b; j > 0; j -= j & -j) {
				odp += bit[i][j];
			}
		}
		return odp;
	}

	int daj(int a, int b, int c, int d) {
		return prefix(c, d) - prefix(c, b - 1) - prefix(a - 1, d) + prefix(a - 1, b - 1);
	}
};





class intervalac {
	int n;
	struct node {
		int in = 0;
		node* l = nullptr;
		node* r = nullptr;
	};
	node* root = new node;
	
	void propagate(node* s) {
		if (s->l == nullptr) s->l = new node;
		if (s->r == nullptr) s->r = new node;
		return;
	}
	
	void zmen(node*s, int l, int r, int a, int k){
		if (l > a || r < a) return;
		if (a <= l && r <= a) {
			s->in += k;
			return;
		}
		int m = (l + r) / 2;
		propagate(s);
		zmen(s->l, l, m, a, k); zmen(s->r, m + 1, r, a, k);
		s->in = s->l->in + s->r->in;
		return;
	}

	int daj(node* s, int l, int r, int a, int b) {
		if (l > b || r < a) return 0;
		if (a <= l && r <= b) return s->in;
		propagate(s);
		int m = (l + r) / 2;
		return daj(s->l, l, m, a, b) + daj(s->r, m + 1, r, a, b);
	}

public:
	intervalac(int vel) {
		n = vel;
		return;
	}
	void zmen(int a, int k) {
		zmen(root, 0, n - 1, a, k);
		return;
	}
	int daj(int a, int b) {
		return daj(root, 0, n - 1, a, b);
	}
};

struct udalost {
	int b, a1, a2, t;
	bool operator<(const udalost& other) const {
		if (b == other.b) {
			return t > other.t;
		}
		return b < other.b;
	}
};

struct udalost3 {
	int c, a1, b1, a2, b2, t;
	bool operator<(const udalost3& other) const {
		if (c == other.c) {
			return t > other.t;
		}
		return c < other.c;
	}
};

void combo2(int& a, int& b) {
	int a2 = (a + b), b2 = (a - b);
	a = a2, b = b2;
	return;
}

void combo3(int& a, int& b, int &c) {
	int a2 = (a + b + c), b2 = (a + b - c), c2 = (a - b);
	a = a2, b = b2, c = c2;
	return;
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int tt; cin >> tt;
	if (tt == 1) {
		int n, d, m; cin >> n >> d >> m;
		vec<int> p(n);
		For(i, n) cin >> p[i];
		intervalac seg(m + d +1);
		ll vys = 0;
		For(i, n) {
			seg.zmen(p[i] + d, 1);
			vys += (seg.daj(p[i] - d + d, p[i] + d + d) - 1);
		}
		cout << vys << '\n';
		return 0;
	}
	if(tt == 2){
		int n, d, m; cin >> n >> d >> m;
		vec<udalost> u;
		For(i, n) {
			int a, b; cin >> a >> b;
			int a1 = a + d, b1 = b, a2 = a, b2 = b + d, a3 = a - d, b3 = b, a4 = a, b4 = b - d;
			combo2(a, b), combo2(a1, b1), combo2(a2, b2), combo2(a3, b3), combo2(a4, b4);
			u.push_back({ b, a, a, 0 });
			u.push_back({ b2, a3, a2, 1 });
			u.push_back({ b1, a4, a1, -1 });
		}
		sort(u.begin(), u.end());
		ll vys = 0;
		intervalac seg(3 * m + 2 * d + 1);
		For(i, u.size()) {
			if (u[i].t == -1) {
				vys += seg.daj(u[i].a1 + m + d, u[i].a2 + m + d);
			}
			if (u[i].t == 0) {
				seg.zmen(u[i].a1 + m + d, 1);
			}
			if (u[i].t == 1) {
				vys -= seg.daj(u[i].a1 + m + d, u[i].a2 + m + d);
			}
		}
		vys -= n;
		cout << vys / 2 << '\n';
		return 0;
	}
	if (tt == 3) {
		int n, d, m; cin >> n >> d >> m;
		vec<udalost3> u;
		For(i, n) {
			int a, b, c; cin >> a >> b >> c;
			int a3 = a, b3 = b - d, c3 = c;
			int a6 = a + d, b6 = b, c6 = c;
			int a2 = a - d, b2 = b, c2 = c;
			int a5 = a, b5 = b + d, c5 = c;
			combo3(a, b, c), combo3(a3, b3, c3), combo3(a6, b6, c6), combo3(a2, b2, c2), combo3(a5, b5, c5);
			u.push_back({ c3, a3, b3, a6, b6, -1 });
			u.push_back({ c, a, b, a, b, 0 });
			u.push_back({ c2, a2, b2, a5, b5, 1 });
		}
		sort(u.begin(), u.end());
		ll vys = 0;
		intervalac2d seg(4 * m + 2 * d + 10, 4 * m + 2 * d + 10);
		For(i, u.size()) {
			if (u[i].t == -1) {
				vys += seg.daj(u[i].a1 + m + d, u[i].b1 + m + d, u[i].a2 + m + d, u[i].b2 + m + d);
			}
			if (u[i].t == 0) {
				seg.zmen(u[i].a1 + m + d, u[i].b1 + m + d, 1);
			}
			if (u[i].t == 1) {
				vys -= seg.daj(u[i].a1 + m + d, u[i].b1 + m + d, u[i].a2 + m + d, u[i].b2 + m + d);
			}
		}
		vys -= n;
		cout << vys / 2 << '\n';
		return 0;
		return 0;
	}
	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: 0 / 10
• Subtask 11: 0 / 10
• Subtask 12: 0 / 10
• Subtask 13: 0 / 10