Submission #1361149

#TimeUsernameProblemLanguageResultExecution timeMemory
1361149Hora000Sails (IOI07_sails)C++20
100 / 100
251 ms2760 KiB
#include<bits/stdc++.h>
using namespace std;

vector<int> st;
int n;
int m = 100000;

void update(int l, int r, int i, int ch, int x){
    if(l == r){
        st[x] += ch;
        return;
    }
    int mid = (l + r) / 2;
    if(i <= mid) update(l, mid, i, ch, 2 * x + 1);
    else update(mid + 1, r, i, ch, 2 * x + 2);
    st[x] = st[2 * x + 1] + st[2 * x + 2];
}

int query(int lq, int rq, int l, int r, int x){
    if(lq > r || l > rq) return 0;
    if(lq <= l && r <= rq) return st[x];
    int mid = (l + r) / 2;
    return query(lq, rq, l, mid, 2 * x + 1) + query(lq, rq, mid + 1, r, 2 * x + 2);
}

void upd(int l, int r){
    update(0, m, l, +1, 0);
    if(r + 1 <= m) update(0, m, r + 1, -1, 0);
    //cout << l << " - " << r << "\n";
}

int searchfirst(int x){
    int lo = 0, hi = m + 1, mid; //rossz, jo
    while(lo + 1 < hi){
        mid = (lo + hi) / 2;
        if(query(0, mid, 0, m, 0) <= x) hi = mid;
        else lo = mid;
    }
    return hi;
}

int searchlast(int x){
    int lo = 1, hi = m + 1, mid; //rossz, jo
    while(lo + 1 < hi){
        mid = (lo + hi) / 2;
        if(query(0, mid, 0, m, 0) < x) hi = mid;
        else lo = mid;
    }
    return lo;
}

int main(){
    cin >> n;
    //m = n;
    st.resize(4 * m + 4, 0);
    vector<array<int, 2>> a(n);
    for(int i = 0; i < n; i++) cin >> a[i][0] >> a[i][1];
    sort(a.begin(), a.end());
    for(auto [h, k] : a){
        int x = query(0, h - k + 1, 0, m, 0);
        //cout << h - k + 1 << " " << x << "\n";
        int i = min(searchlast(x), h);
        if(i != h) upd(i + 1, h); //ha van mas elotte
        int j = max(searchfirst(x), 1);
        int db = i - (h - k + 1) + 1;
        upd(j, j + db - 1);
        /*cout << h << " " << k << ": " << i << " " << j << " " << db << " " << x << "\n";
        for(int o = 0; o <= m; o++){
            int x = query(0, o, 0, m, 0);
            cout << x << " ";
        }
        cout << "\n";*/
    }
    long long ans = 0;
    for(int i = 0; i <= m; i++){
        long long x = (long long)query(0, i, 0, m, 0);
        ans += (x * (x - 1)) / 2;
        //cout << x << " ";
    }
    cout << ans;
}
#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...