oj.uz

Submission #410328

# Submission time Handle Problem Language Result Execution time Memory
410328 2021-05-22T14:02:30 Z AugustinasJucas Pairs (IOI07_pairs) C++14
60 / 100
 221 ms 14840 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;
	
}
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.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 2 ms 204 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 1060 KB Output is correct
2 Correct 35 ms 972 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 1436 KB Output is correct
2 Correct 51 ms 1444 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 1544 KB Output is correct
2 Correct 54 ms 1548 KB Output is correct
3 Correct 66 ms 1556 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 10800 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 12840 KB Output is correct
2 Correct 98 ms 12828 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 13096 KB Output is correct
2 Correct 129 ms 13080 KB Output is correct
3 Correct 121 ms 13092 KB Output is correct
4 Correct 117 ms 13092 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 14756 KB Output is correct
2 Correct 221 ms 14840 KB Output is correct
3 Correct 141 ms 13596 KB Output is correct
4 Correct 137 ms 13428 KB Output is correct

Subtask #10
0 / 10.0

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

Subtask #11
0 / 10.0

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

Subtask #12
0 / 10.0

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

Subtask #13
0 / 10.0

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