oj.uz

Submission #410515

# Submission time Handle Problem Language Result Execution time Memory
410515 2021-05-22T20:56:10 Z AugustinasJucas Pairs (IOI07_pairs) C++14
100 / 100
 1020 ms 444948 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
struct seg_tree{
	struct node{
		int val = 0;
		int l, r;
	};
	vector<node> tree;
	int n;
	int dbInd = 0;
	void build(int v){
		if(v >= n){
			tree[v].l = tree[v].r = dbInd++;
		}else{
			build(v*2); build(v*2+1);
			tree[v].l = tree[v*2].l;
			tree[v].r = tree[v*2+1].r;
		}
	}
	seg_tree(int dd){
		n = dd;
		tree.resize(2 * n + 1);
		build(1);
	}
	void change(int v, int l, int r, int x){
		if(l <= tree[v].l && tree[v].r <= r){
			tree[v].val += x;
		}else if(tree[v].r < l || r < tree[v].l){
			
		}else{
			change(v*2, l, r, x);
			change(v*2+1, l, r, x);
			tree[v].val = tree[v*2].val + tree[v*2+1].val;
		}
	}
	int find(int v, int l, int r){
		if(l <= tree[v].l && tree[v].r <= r){
			return tree[v].val;
		}else if(tree[v].r < l || r < tree[v].l){
			return 0;
		}else{
			return find(v*2, l, r) + find(v*2+1, l, r);
		}
	}
};
long long f1(vector<int> &mas, int X){ // N log N
	// mas isrikiuotas
	long long ret = 0;
	for(auto x : mas){
	//	cout << x << " prd " << upper_bound(mas.begin(), mas.end(), x + X) - lower_bound(mas.begin(), mas.end(), x - X) << endl;
		ret += upper_bound(mas.begin(), mas.end(), x + X) - lower_bound(mas.begin(), mas.end(), x - X)-1;
	}
	return ret;
}
long long f2(vector<pair<int, int> > &ms, int d){
	const int dd = 150001;
	vector<vector<int> > pts(dd);
	vector<pair<int, int> > mas;
	for(int i = 0; i < (int)ms.size(); i++){
		int X = ms[i].first + ms[i].second;
		int Y = ms[i].first - ms[i].second;
		pts[X].push_back(Y);
	}
	seg_tree medis(dd * 2 + 10);
	sort(mas.begin(), mas.end());
	long long ans = 0;
	for(int i = 0; i < dd; i++){
		if(i-d-1 >= 0){
			for(auto x : pts[i-d-1]){
				//cout << "X = " << x << endl;
				medis.change(1, x +dd, x + dd, -1);
			}
		}
		sort(pts[i].begin(), pts[i].end());
		for(int j = 0; j < (int)pts[i].size(); j++){
			ans += upper_bound(pts[i].begin() + j, pts[i].end(), pts[i][j] + d) - pts[i].begin() - j -1;
			 //cout << "prd " << (int)( upper_bound(pts[i].begin() + j + 1, pts[i].end(), pts[i][j] + d) - pts[i].begin() - j - 2) << endl;
			ans += medis.find(1, pts[i][j]-d + dd, pts[i][j]+d + dd);
		}
		
		for(auto x : pts[i]){
			medis.change(1, x+dd, x + dd, 1);
		}
	}
	return ans;	
}
void dar(vector<vector<int> > &mas, vector<vector<int> > &pref){ // precalc pref
	int n = mas.size();
	int m = mas[0].size();
	for(int i = 0; i < n; i++){
		int sm = 0;
		for(int j = 0; j < m; j++){
			sm += mas[i][j];
			pref[i][j] = (i == 0 ? 0 : pref[i-1][j]) + sm;
		}
	}
}
int ad = 0, ak = 0, vd = 0, vk = 0;
int fd(vector<vector<int> > &pref, int x1, int y1, int x2, int y2){
	ad = 0, ak = 0, vd = 0, vk = 0;
	ad = pref[x2][y2];
	if(x1 != 0) ak = pref[x1-1][y2];
	if(y1 != 0) vd = pref[x2][y1-1];
	if(y1 != 0 && x1 != 0) vk = pref[x1-1][y1-1];
	return ad - ak - vd + vk;
}
int fdd(vector<vector<int> > &mas, int X, int Y, int dst){
	int ret = 0;
	//cout << "darau\n";
	//for(auto x : mas)
	for(int i = 0; i < (int)mas.size(); i++){
		for(int j = 0;  j < (int)mas.size(); j++){
			if(max(abs(i-X), abs(j - Y)) <= dst) ret += mas[i][j];
		}
	}
	//for(auto x : mas) if(abs(x.second.first - X) + abs(x.second.second - Y) <= dst) ret ++;
	return ret;
}
int fddd(vector<pair<int, pair<int, int> > > mas, int X, int y, int z, int d){
	int ret = 0;
	for(auto x : mas){
		if(x.first != X) continue;
		if(abs(x.first - X) + abs(x.second.first - y) + abs(x.second.second - z) <= d){
			ret++;
		}
	}
	return ret;
}
const int dd = 76;
int sm[dd+1][dd+1][dd+1][3*dd+1] = {};
long long f3(vector<pair<int, pair<int, int> > > &mas, int d){
	//cout << "STOP!" << endl;
	//long long ps = 0;
	//for(auto x : mas) for(auto y : mas) if(abs(x.first - y.first) + abs(x.second.first - y.second.first) + abs(x.second.second - y.second.second) <= d) ps++;
	//cout << (ps-(int)mas.size())/2 << "  ";
	vector<vector<vector<int> > > trans, pref;
	 
	trans.resize(dd+1);
	for(auto &x : trans){
		x.resize(dd*3 + 1);
		for(auto &y : x) y.resize(dd*3 + 1);
		for(auto &z : x) for(auto &g : z) g = 0;
	}
	pref = trans;
	vector<vector<pair<int, int> > > pts;
	pts.resize(dd + 1);
	for(auto x : mas){
		int X = x.second.first;
		int Y = x.second.second;
		trans[x.first][X+Y][X-Y+dd]++;
		pts[x.first].push_back({X+Y, X-Y + dd});
		//cout << "trans " << X+Y << "; " << X-Y + dd << ", aukstuje " << x.first << endl;
	}

	
	for(int i = 0; i <= dd; i++){
		dar(trans[i], pref[i]);
	}
	
	int X, Y, x1, x2, y1, y2;
	for(int i = 0; i <= dd; i++){
		for(int j = 0; j <= dd; j++){
			for(int h = 0; h <= dd; h++){
				for(int l = 0; l <= 3*dd; l++){ // jei turiu tik pozicija i-ajame aukste su koordinatem [j; h] ir d = l, kiek pasieksiu?
					X = j + h;
					Y = j - h + dd;
					
					x1 = min(max(X - l, 0), dd*3);
					y1 = min(max(Y - l, 0), dd*3);
					x2 = max(min(X + l, dd*3), 0);
					y2 = max(min(Y + l, dd*3), 0);
					//cout << X << "; " << Y << ":  " << x1 << "; " << y1 << ";   " << x2 << "; " << y2 << endl;
					sm[i][j][h][l] = fd(pref[i], x1, y1, x2, y2);
					//if(fd(pref[i], x1, y1, x2, y2) != fddd(mas, i, j, h, l) ) cout << "sakau " << fd(pref[i], x1, y1, x2, y2) << " vs " << fddd(mas, i, j, h, l) << ", x=" << i << ", y=" << j << ", z=" << h <<", l = " << l << endl;
				}
			}
		}
	}
	long long ans = 0;
	for(auto x : mas){
		int H, X, Y, L;
		for(int i = -d ; i <= d; i++){
			H = x.first + i;
			if(H < 0 || H > dd) continue;
			X = x.second.first;
			Y = x.second.second;
			L = d - abs(i);
			//cout << "Sm[" << H << "][" << X << "][" << Y << "][" << L << "] = " << sm[H][X][Y][L] << endl;
			ans += sm[H][X][Y][L];
		}
		ans--;
	}
	return ans/2ll;
	
}
/*
3 2 26 10
8 2 2
9 3 8
*/
void gen(){
	int n = rand() % 4; int d = rand()%30 + 2;
	cout << "3 " << n << " " << d << " 10" << "\n";
	for(int i = 0; i < n; i++){
		cout << rand()%10 << " " << rand()%10 << " " << rand() % 10 << endl;
	}
	cout << endl;
}
int main(){
	srand(time(0));
	//gen();
	int B, n, d, m; cin >> B >> n >> d >> m;
	if(B == 1){
		vector<int> ms(n); for(auto &x : ms) cin >> x;
		sort(ms.begin(), ms.end());
		cout << f1(ms, d) /2ll;
		return 0;
	}else if(B == 2){
		vector<pair<int, int> > ms(n);
		for(auto &x : ms) cin >> x.first >> x.second;
		cout << f2(ms, d);
	}else{
		vector<pair<int, pair<int, int> > > ms(n);
		for(auto &x : ms) cin >> x.first >> x.second.first >> x.second.second;
		cout << f3(ms, d);
	}
	
	return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 696 KB Output is correct
2 Correct 35 ms 692 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 588 KB Output is correct
2 Correct 52 ms 684 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 680 KB Output is correct
2 Correct 54 ms 588 KB Output is correct
3 Correct 55 ms 588 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10900 KB Output is correct
2 Correct 11 ms 10800 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 12220 KB Output is correct
2 Correct 92 ms 12216 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 12368 KB Output is correct
2 Correct 120 ms 12372 KB Output is correct
3 Correct 121 ms 12208 KB Output is correct
4 Correct 115 ms 12316 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 13696 KB Output is correct
2 Correct 198 ms 13616 KB Output is correct
3 Correct 134 ms 12348 KB Output is correct
4 Correct 127 ms 12480 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 713 ms 442332 KB Output is correct
2 Correct 703 ms 442436 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 759 ms 444792 KB Output is correct
2 Correct 767 ms 444684 KB Output is correct
3 Correct 769 ms 444680 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 825 ms 444612 KB Output is correct
2 Correct 977 ms 444624 KB Output is correct
3 Correct 1016 ms 444596 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 917 ms 444804 KB Output is correct
2 Correct 998 ms 444860 KB Output is correct
3 Correct 1020 ms 444948 KB Output is correct