Submission #410328

#	Time	Username	Problem	Language	Result	Execution time	Memory
410328		AugustinasJucas	Pairs (IOI07_pairs)	C++14	60 / 100	221 ms	14840 KiB

pairs

#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;
	
}
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);
	}
	
	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