# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
966904 |
2024-04-20T15:12:26 Z |
Trisanu_Das |
Sails (IOI07_sails) |
C++17 |
|
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);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
348 KB |
Output is correct |
2 |
Correct |
2 ms |
860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
604 KB |
Output is correct |
2 |
Correct |
11 ms |
860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
1024 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
1492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
33 ms |
2272 KB |
Output is correct |
2 |
Correct |
32 ms |
2180 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
39 ms |
2384 KB |
Output is correct |
2 |
Correct |
30 ms |
2048 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
44 ms |
2540 KB |
Output is correct |
2 |
Correct |
30 ms |
2388 KB |
Output is correct |