oj.uz

Submission #410462

# Submission time Handle Problem Language Result Execution time Memory
410462 2021-05-22T18:01:33 Z AugustinasJucas Pairs (IOI07_pairs) C++14
60 / 100
 497 ms 336072 KB 
#include <bits/stdc++.h>
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 fd(vector<vector<int> > &pref, int x1, int y1, int x2, int y2){
	int 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;
}
const int dd = 75;
int sm[76][76][76][76] = {};
long long f3(vector<pair<int, pair<int, int> > > &mas, int d){
	vector<vector<vector<int> > > trans, pref;
	 
	trans.resize(76);
	for(auto &x : trans){
		x.resize(230);
		for(auto &y : x) y.resize(230);
	}
	pref = trans;
	vector<vector<pair<int, int> > > pts;
	pts.resize(75 + 1);
	for(auto x : mas){
		int X = x.second.first;
		int Y = x.second.second;
		trans[x.first][X+Y][X-Y+dd] = 1;
		pts[x.first].push_back({X+Y, X-Y + dd});
	}
	
	for(int i = 0; i <= 75; i++){
		dar(trans[i], pref[i]);
	}
	
	for(int i = 0; i <= 75; i++){
		for(int j = 0; j <= 75; j++){
			for(int h = 0; h <= 75; h++){
				for(int l = 0; l <= 75; l++){ // jei turiu tik pozicija i-ajame aukste su koordinatem [j; h] ir d = l, kiek pasieksiu?
					int X = j + h;
					int Y = j - h + dd;
					
					int x1 = min(max(X - l, 0), 75);
					int y1 = min(max(Y - l, 0), 75);
					int x2 = max(min(X + l, 229), 0);
					int y2 = max(min(Y + l, 229), 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 + 1; i <= d-1; i++){
			H = x.first + i;
			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 588 KB Output is correct
2 Correct 36 ms 588 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 680 KB Output is correct
2 Correct 69 ms 588 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 588 KB Output is correct
2 Correct 54 ms 700 KB Output is correct
3 Correct 53 ms 696 KB Output is correct

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 12228 KB Output is correct
2 Correct 96 ms 12224 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 12372 KB Output is correct
2 Correct 123 ms 12376 KB Output is correct
3 Correct 118 ms 12348 KB Output is correct
4 Correct 136 ms 12316 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 13692 KB Output is correct
2 Correct 223 ms 13692 KB Output is correct
3 Correct 141 ms 12336 KB Output is correct
4 Correct 132 ms 12420 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 442 ms 331144 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 314 ms 165760 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 497 ms 335748 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 494 ms 336072 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -