Submission #1323253

#TimeUsernameProblemLanguageResultExecution timeMemory
132325324ta_tdanhSails (IOI07_sails)C++20
90 / 100
106 ms4344 KiB
#include <bits/stdc++.h>
#define endl '\n'
#define fi first
#define se second
#define eb emplace_back
#define pb push_back
#define ALL(A) A.begin(), A.end()
#define FOR(i, l, r) for (int i = l; i <= r; i++)
#define FOR2(i, l, r) for (int i = l; i >= r; i--)
#define ce cout<<endl;
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using pii = pair<int, int>;
using str = string;
using T = pair<ll,int>;
const ll INF = 1e9 + 1;
const int N = 1e5;
struct SegmentTree {
    int n;
    vector<int> st, lz;

    SegmentTree(int _n) {
        n = _n;
        st.assign(4 * n + 5, 0);
        lz.assign(4 * n + 5, 0);
    }

    void down(int id) {
        if (lz[id] == 0) return;
        st[id * 2] += lz[id];
        lz[id * 2] += lz[id];
        st[id * 2 + 1] += lz[id];
        lz[id * 2 + 1] += lz[id];
        lz[id] = 0;
    }

    void build(int id, int l, int r, vector<int>& H) {
        if (l == r) {
            st[id] = H[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(id * 2, l, mid, H);
        build(id * 2 + 1, mid + 1, r, H);
        st[id] = max(st[id * 2], st[id * 2 + 1]); 
    }

    void update(int id, int l, int r, int u, int v) {
        if (u > v || u > r || v < l) return;
        if (u <= l && r <= v) {
            st[id]++;
            lz[id]++;
            return;
        }
        down(id);
        int mid = (l + r) >> 1;
        update(id * 2, l, mid, u, v);
        update(id * 2 + 1, mid + 1, r, u, v);
        st[id] = max(st[id * 2], st[id * 2 + 1]);
    }

    int findFirst(int id, int l, int r, int u, int v, int x) {
        if (l > v || r < u || st[id] < x) return n + 1;
        if (l == r) return l;
        down(id);
        int mid = (l + r) >> 1;
        int res = findFirst(id * 2, l, mid, u, v, x);
        if (res == n + 1) {
            res = findFirst(id * 2 + 1, mid + 1, r, u, v, x);
        }
        return res;
    }

    int getVal(int id, int l, int r, int pos) {
        if (l == r) return st[id];
        down(id);
        int mid = (l + r) >> 1;
        if (pos <= mid) return getVal(id * 2, l, mid, pos);
        else return getVal(id * 2 + 1, mid + 1, r, pos);
    }

    void upd(int l, int r) { update(1, 1, n, l, r); }
    int queryFirst(int u ,int v, int x) { return findFirst(1, 1, n,u , v, x); }
    int get(int pos) { return getVal(1, 1, n, pos); }
};

void solve() {
    int n ;
    cin >> n;
    vector<pii> masts(n + 1);
    FOR(i,1,n) cin >> masts[i].fi >> masts[i].se;
    sort(masts.begin() + 1 , masts.end());
    SegmentTree st(N);
    ll res = 0;
    FOR(i,1,n){
        int h = masts[i].fi , k = masts[i].se;
        int low = N - h + 1;
        int L = low;
        int R = low + k - 1;
        int val_at_r = st.get(low + k - 1);
        int first_r = st.queryFirst(low , N , val_at_r);
        int last_r = st.queryFirst(low , N , val_at_r + 1) - 1;
        int num_at_valR = R - first_r + 1;
        if(L <= first_r - 1) st.upd(L , first_r - 1);
        st.upd(last_r  - num_at_valR + 1 , last_r);



    }
    FOR(i,1,N){
        int cnt= st.get(i);
        res += cnt * (cnt - 1)  / 2 ;
    }
    cout << res <<endl;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t = 1;
    while (t--) {
        solve();
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...