This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
const int N = 1e5 + 5;
int n;
int dif[N];
set<int> st;
void add(int i, int x) {
dif[i] += x;
if (dif[i]) {
st.insert(i);
} else {
st.erase(i);
}
}
void upd(int i, int j) {
add(i, 1);
add(j + 1, -1);
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
vector<array<int, 2>> a(n);
for (auto &x : a) {
cin >> x[0] >> x[1];
}
sort(a.begin(), a.end());
int l = a.back()[0];
st.insert(1);
st.insert(l + 1);
for (auto [h, k] : a) {
auto it = st.upper_bound({h - k + 1});
int l = *prev(it), r = *it - 1;
if (r < h) {
upd(r + 1, h);
k -= h - r;
}
if (k > 0) {
upd(l, l + k - 1);
}
}
long long res = 0;
int cnt = 0;
for (int i = 1; i <= l; ++i) {
cnt += dif[i];
res += (long long) cnt * (cnt - 1) / 2;
}
cout << res;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |