Submission #1362341

#TimeUsernameProblemLanguageResultExecution timeMemory
1362341qwertzztrewqSails (IOI07_sails)C++20
100 / 100
97 ms6360 KiB
#include <bits/stdc++.h>
using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define pb push_back
#define fst first
#define snd second

template <typename t>
using vv = vector<t>;
template <typename a, typename b>
using pp = pair<a, b>;

typedef long long ll;
typedef double db;

const int mod = 1e9 + 7;

vv<pp<ll, ll>> st;
vv<int> lv;
int s = 1;

void push(int node) {
    int u = node << 1;
    lv[u] += lv[node];
    st[u].fst += lv[node];
    st[u].snd += lv[node];
    lv[++u] += lv[node];
    st[u].fst += lv[node];
    st[u].snd += lv[node];
    lv[node] = 0;
}

void upd(int x, int y, int l, int r, int node, int v) {
    if (x > r || y < l) return;
    if (x <= l && y >= r) {
        st[node].fst += v;
        st[node].snd += v;
        lv[node] += v;
        return;
    }
    int m = (l + r) / 2;
    push(node);
    upd(x, y, l, m, node * 2, v);
    upd(x, y, m + 1, r, node * 2 + 1, v);
    st[node].fst = st[node * 2 + 1].fst;
    st[node].snd = st[node * 2].snd;
}

int cat(int l, int r, int node, int v) {
    if (l == r) return l;
    int m = (l + r) / 2;
    push(node);
    if (st[node * 2].fst <= v) return cat(l, m, node * 2, v);
    return cat(m + 1, r, node * 2 + 1, v);
}

int dog(int l, int r, int node, int v) {
    if (l == r) return l;
    int m = (l + r) / 2;
    push(node);
    if (st[node * 2 + 1].snd >= v) return dog(m + 1, r, node * 2 + 1, v);
    return dog(l, m, node * 2, v);
}

void get(int node) {
    if (!node) return;
    get(node >> 1);
    if (node < s) push(node);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    vv<pp<int, int>> idk(n);
    for (auto& p : idk) cin >> p.fst >> p.snd;
    sort(all(idk));
    while (s < idk.back().fst) s <<= 1;
    st.assign(s << 1, {0, 0});
    lv.assign(s << 1, 0);
    for (auto [h, k] : idk) {
        int p = h - k;
        get(p + s);
        int x = st[p + s].fst;
        int l = cat(0, s - 1, 1, x), r = dog(0, s - 1, 1, x);
        r = min(r, h - 1);
        int cnt = r - p + 1;
        if (cnt) upd(l, l + cnt - 1, 0, s - 1, 1, 1);
        if (r + 1 <= h - 1) upd(r + 1, h - 1, 0, s - 1, 1, 1);
    }
    for (int i = 1; i < s; i++) push(i);
    ll ans = 0;
    for (int i = s; i < s + idk.back().fst; i++) ans += st[i].fst * (st[i].fst - 1) / 2;
    cout << ans;
    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...