oj.uz

Submission #966904

# Submission time Handle Problem Language Result Execution time Memory
966904 2024-04-20T15:12:26 Z Trisanu_Das Sails (IOI07_sails) C++17
100 / 100
 44 ms 2540 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
 
int n, BIT[N];
long long ans;
 
void upd(int idx, int val) {
	for(; idx < N; idx += (idx & -idx)) BIT[idx] += val;
}
 
int qry(int idx) {
	int ans = 0;
	for(; idx; idx -= (idx & -idx)) ans += BIT[idx];
	return ans;
}
 
int lb(int val) {
	int i = 0;
	for(int j = 1 << 17; j /= 2;) if(i + j < N && BIT[i + j] < val) val -= BIT[i += j];
	return i + 1;
}
 
int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);
	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 = qry(N - h + k - 1);
		int l = lb(v), r = lb(v + 1) - 1;
		if(N - h < l) {
			upd(N - h, 1);
			upd(l, -1);
		}
		upd(r - (k - max(0, l - (N - h))) + 1, 1);
		upd(r + 1, -1);
	}
	for(int i = 1; i < N; ++i) {
		long long v = qry(i);
		ans += v * (v - 1);
    }
	cout << (ans >> 1);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 604 KB Output is correct
2 Correct 11 ms 860 KB Output is correct

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 2272 KB Output is correct
2 Correct 32 ms 2180 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 2384 KB Output is correct
2 Correct 30 ms 2048 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 2540 KB Output is correct
2 Correct 30 ms 2388 KB Output is correct