oj.uz

Submission #529346

# Submission time Handle Problem Language Result Execution time Memory
529346 2022-02-22T20:13:44 Z sidon Sails (IOI07_sails) C++17
100 / 100
 55 ms 2392 KB 
#include <bits/stdc++.h>
using namespace std;

const int Z = 1e5+3;

int N, F[Z];
int64_t ans;

void add(int i, int v) {
	for(; i < Z; i += i&-i) F[i] += v;
}

int get(int i) {
	int v = 0;
	for(; i > 0; i -= i&-i) v += F[i];
	return v;
}

int lowerBound(int v) {
	int i = 0;
	for(int j = 1<<17; j /= 2; )
		if(i + j < Z && F[i + j] < v) v -= F[i += j];
	return i + 1;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);

	cin >> N;

	array<int, 2> a[N];

	for(auto &[h, k] : a)
		cin >> h >> k;

	sort(a, a+N);

	for(auto &[h, k] : a) {
		int v = get(Z - h + k - 1);
		int l = lowerBound(v), r = lowerBound(v + 1) - 1;

		if(Z - h < l) {
			add(Z - h, 1);
			add(l, -1);
		}

		add(r - (k - max(0, l - (Z - h))) + 1, 1);
		add(r + 1, -1);
	}

	for(int i = 1; i < Z; ++i) {
		int64_t v = get(i);
		ans += v * (v - 1);
	}

	cout << (ans >> 1);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 2 ms 716 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 448 KB Output is correct
2 Correct 17 ms 844 KB Output is correct

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 2144 KB Output is correct
2 Correct 44 ms 2108 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 2244 KB Output is correct
2 Correct 31 ms 1992 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 2392 KB Output is correct
2 Correct 35 ms 1952 KB Output is correct