Submission #1176680

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176680		sano	Pairs (IOI07_pairs)	C++20	30 / 100	4096 ms	139032 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 intervalac {
	int n;
	struct node {
		int in = 0;
		int lp = 0;
		node* left = nullptr;
		node* right = nullptr;
	};
	node* root = new node;

	void apply(node* s, int l, int r, int x) {
		s->in += (r - l + 1) * x;
		s->lp += x;
		return;
	}

	void propagate(node* s, int l, int r) {
		if (s->left == nullptr) s->left = new node;
		if (s->right == nullptr) s->right = new node;
		int m = (l + r) / 2;
		apply(s->left, l, m, s->lp);
		apply(s->right, m + 1, r, s->lp);
		s->lp = 0;
	}

	void zmen(node* s, int l, int r, int a, int b, int k) {
		if (l > b || r < a) return;
		if (a <= l && r <= b) {
			s->in += k * (r - l + 1);
			s->lp += k;
			return;
		}
		propagate(s, l, r);
		int m = (l + r) / 2;
		zmen(s->left, l, m, a, b, k), zmen(s->right, m + 1, r, a, b, k);
		s->in = s->left->in + s->right->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, l, r);
		int m = (l + r) / 2;
		return daj(s->left, l, m, a, b) + daj(s->right, m + 1, r, a, b);
	}

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

struct mojo {
	int a, b, c;
	bool operator<(const mojo& other) const {
		if (a == other.a) {
			if (b == other.b) {
				return c < other.c;
			}
			return b < other.b;
		}
		return a < other.a;
	}
};

class BIT3d{
	int n, m, p;

	
	map<mojo, int> bit;

	int daj(int a, int b, int c) {
		int vys = 0;
		for (int i = a; i; i -= i & -i) {
			for (int j = b; j; j -= j & -j) {
				for (int k = c; k; k -= k & -k) {
					vys += bit[{i, j, k}];
				}
			}
		}
		return vys;
	}
public:
	BIT3d(int v1, int v2, int v3) {
		n = v1, m = v2, p = v3;
		return;
	}
	void zmen(int a, int b, int c, int h) {
		for (int i = a; i <= n; i += i & -i) {
			for (int j = b; j <= m; j += j & -j) {
				for (int k = c; k <= p; k += k & -k) {
					bit[{i, j, k}] += h;
				}
			}
		}
		return;
	}
	int obdl3d(int a, int b, int c, int d, int e, int f) {
		return daj(d, e, f) - daj(d, e, c - 1) - daj(d, b - 1, f) - daj(a - 1, e, f) + daj(a - 1, b - 1, f) + daj(a - 1, e, c - 1) + daj(d, b - 1, c - 1) - daj(a - 1, b - 1, c - 1);
	}
};

void combo(int& a, int& b, int& c) {
	int a1 = (a + b + c), b1 = (a + b - c), c1 = a - b;
	a = a1, b = b1, c = c1;
	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+1);
		ll vys = 0;
		For(i, n) {
			seg.zmen(p[i], p[i], 1);
			vys += (seg.daj(p[i] - d, p[i] + d) - 1);
		}
		cout << vys << '\n';
		return 0;
	}
	if(tt == 2){
		
	}
	if (tt == 3) {
		int n, h, m; cin >> n >> h >> m;
		h = min(h, 2 * m);
		vec<vec<int>> p(n, vec<int>(3));
		For(i, n) For(j, 3) cin >> p[i][j];
		BIT3d seg(10 * (m + 1), 10 * (m + 1), 10 * (m + 1));
		ll vys = 0;
		For(i, n) {
			int a = p[i][0] - h, b = p[i][1], c = p[i][2];
			int d = (p[i][0] + h), e = b, f = c;
			int x = p[i][0], y = p[i][1], z = p[i][2];
			int suc = x + y + z;
			combo(a, b, c); combo(d, e, f); combo(x, y, z);
			vys += seg.obdl3d(a + 3*m, b + 3 * m, c + 3 * m, d + 3 * m, e + 3 * m, f + 3 * m);
			seg.zmen(x + 3*m, y + 3*m, z + 3*m, 1);
		}
		cout << vys << '\n';
		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: 0 / 7
• Subtask 7: 0 / 7
• Subtask 8: 0 / 8
• Subtask 9: 0 / 8
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10
• Subtask 12: 0 / 10
• Subtask 13: 0 / 10