oj.uz

Submission #410491

# Submission time Handle Problem Language Result Execution time Memory
410491 2021-05-22T19:38:32 Z AugustinasJucas Pairs (IOI07_pairs) C++14
70 / 100
 666 ms 209536 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;
}
const int dd = 80;
int sm[dd+1][dd+1][dd+1][dd+1] = {};
long long f3(vector<pair<int, pair<int, int> > > &mas, int d){
	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);
	}
	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 <= 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-2);
					y1 = min(max(Y - l, 0), dd*3-2);
					x2 = max(min(X + l, dd*3-2), 0);
					y2 = max(min(Y + l, dd*3-2), 0);
					sm[i][j][h][l] =fd(pref[i], x1, y1, x2, y2);
				}
			}
		}
	}
	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);
			ans += sm[H][X][Y][L];
		}
		ans--;
	}
	return ans/2ll;
	
} 
int main(){
	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 36 ms 684 KB Output is correct
2 Correct 37 ms 700 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 588 KB Output is correct
2 Correct 53 ms 588 KB Output is correct

Subtask #5
6.0 / 6.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 12220 KB Output is correct
2 Correct 103 ms 12352 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 12336 KB Output is correct
2 Correct 122 ms 12332 KB Output is correct
3 Correct 114 ms 12336 KB Output is correct
4 Correct 125 ms 12320 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 13636 KB Output is correct
2 Correct 204 ms 13628 KB Output is correct
3 Correct 136 ms 12348 KB Output is correct
4 Correct 130 ms 12348 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 206916 KB Output is correct
2 Incorrect 341 ms 206940 KB Output isn't correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 393 ms 209448 KB Output is correct
2 Correct 408 ms 209464 KB Output is correct
3 Correct 409 ms 209360 KB Output is correct

Subtask #12
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 450 ms 209148 KB Output is correct
2 Correct 614 ms 209348 KB Output is correct
3 Incorrect 652 ms 209220 KB Output isn't correct

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 544 ms 209464 KB Output is correct
2 Correct 630 ms 209536 KB Output is correct
3 Incorrect 666 ms 209508 KB Output isn't correct