oj.uz

Submission #371015

# Submission time Handle Problem Language Result Execution time Memory
371015 2021-02-25T15:15:33 Z cheissmart Pairs (IOI07_pairs) C++14
60 / 100
 67 ms 5980 KB 
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7;

int n, d, m;

void solve1() {
	vi a(n);
	for(int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(ALL(a));
	ll ans = 0;
	for(int i = 0, j = 0; i < n; i++) {
		while(a[i] - a[j] > d) j++;
		assert(a[i] - a[j] <= d);
		ans += i - j;
	}
	cout << ans << '\n';
}

const int N = 3e5 + 7, offset = 150002;

int bit[N];

void add(int y, int val) {
	y += offset;
	assert(y >= 1);
	for(; y < N; y += y & -y)
		bit[y] += val;
}

int qry(int y) {
	y += offset;
	assert(y >= 1);
	int res = 0;
	for(; y; y -= y & -y)
		res += bit[y];
	return res;
}

void solve2() {
	V<pi> a(n);
	for(int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;
		a[i] = {x - y, x + y};
	}
	V<array<int, 3>> ev;
	ll ans = 0;
	for(int i = 0; i < n; i++) {
		ev.PB({a[i].F, 0, a[i].S});
		ev.PB({a[i].F + d, 1, a[i].S});
	}
	sort(ALL(ev));
	deque<pi> dk;
	for(auto e:ev) {
		if(e[1] == 0) { // add point
			add(e[2], 1);
			dk.EB(e[0], e[2]);
		} else { // qry
			while(dk.size() && dk[0].F < e[0] - 2 * d) {
				add(dk[0].S, -1);
				dk.pop_front();
			}
			int l = max(e[2] - d, -150000), r = min(e[2] + d, 150000);
			ans += qry(r) - qry(l - 1) - 1;
		}
	}
	cout << ans / 2 << '\n';
}


void solve3() {

}

signed main()
{
	IO_OP;

	int b;
	cin >> b >> n >> d >> m;
	if(b == 1) solve1();
	else if(b == 2) solve2();
	else solve3();


}

Subtask #1
6.0 / 6.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

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

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 748 KB Output is correct
2 Correct 19 ms 748 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 748 KB Output is correct
2 Correct 22 ms 748 KB Output is correct
3 Correct 18 ms 748 KB Output is correct

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 4320 KB Output is correct
2 Correct 56 ms 4576 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 4320 KB Output is correct
2 Correct 60 ms 4320 KB Output is correct
3 Correct 62 ms 4320 KB Output is correct
4 Correct 63 ms 4320 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 4320 KB Output is correct
2 Correct 61 ms 5848 KB Output is correct
3 Correct 67 ms 5980 KB Output is correct
4 Correct 64 ms 5720 KB Output is correct

Subtask #10
0 / 10.0

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

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 364 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 364 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 364 KB Output isn't correct
2 Halted 0 ms 0 KB -