Submission #1297715

#TimeUsernameProblemLanguageResultExecution timeMemory
1297715BlockOGSails (IOI07_sails)C++20
100 / 100
59 ms1988 KiB
#include <bits/stdc++.h>

// mrrrowwww meeowwwww :3
// go play vivid/stasis! !! !!! https://vividstasis.gay

#define fo(i, a, b) for (auto i = (a); i < (b); i++)
#define of(i, a, b) for (auto i = (b); i-- > (a);)
#define f first
#define s second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define be(a) a.begin(), a.end()
using namespace std;

int ____init = []{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    return 0;
}();

int a[100001];
int bit[100002];

int get(int i) {
    int res = 0;
    for (i++; i > 0; i -= i & -i) res += bit[i];
    return res;
}

void add(int i, int v) {
    a[i] += v;
    for (i++; i <= 100000; i += i & -i) bit[i] += v;
}

int main() {
    int n; cin >> n;
    vector<pair<int, int>> v(n);
    
    int max_h = 0;
    fo(i, 0, n) cin >> v[i].f >> v[i].s, max_h = max(max_h, v[i].f);
    sort(be(v));
    for (auto [h, k] : v) {
        add(h, -1);

        if (a[h - k]) {
            add(h - k, 1);
        } else {
            int start_hk = get(h - k);
            
            int l = 0, r = h - k;
            while (l < r) {
                int mid = (l + r) / 2;
                if (get(mid) != start_hk) l = mid + 1;
                else r = mid;
            }

            int hk_left = l;
            
            l = h - k, r = h;
            while (l < r) {
                int mid = (l + r) / 2;
                if (get(mid) != start_hk) r = mid;
                else l = mid + 1;
            }

            int hk_right = l;

            add(hk_left, 1);
            add(hk_left + hk_right - (h - k), -1);
            add(hk_right, 1);
        }
    }

    long long res = 0;
    int acc = 0;
    fo(i, 0, max_h) acc += a[i], res += (long long) acc * (acc - 1) / 2;
    cout << res;
}
#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...