제출 #1226806

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1226806		VMaksimoski008	Sails (IOI07_sails)	C++20	100 / 100	97 ms	1984 KiB

sails

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 5;

struct fenwick {
    int n;
    vector<ll> tree;

    fenwick(int _n) : n(_n+10), tree(n+20) {}

    void update(int p, ll v) {
        for(p++; p<n; p+=p&-p) tree[p] += v;
    }

    ll query(int p) {
        ll ans = 0;
        for(p++; p; p-=p&-p) ans += tree[p];
        return ans;
    }

    void update(int l, int r, ll v) {
        update(l, v);
        update(r+1, -v);
    }
} fwt(N);

signed main() {
    int n; cin >> n;
    vector<array<int, 2> > a(n+1);
    for(int i=1; i<=n; i++) cin >> a[i][0] >> a[i][1];
    sort(a.begin()+1, a.end());

    ll ans = 0;
    fwt.update(0, 0, (ll)1e10);
    for(int i=1; i<=n; i++) {
        int R = a[i][0], L = a[i][0]-a[i][1]+1;
        if(fwt.query(L) < fwt.query(L-1)) {
            fwt.update(L, R, 1);
            continue;
        }

        int l=L, r=R, c=1;
        while(l <= r) {
            int mid = (l + r) / 2;
            if(fwt.query(L) == fwt.query(mid)) c = mid-L+1, l = mid + 1;
            else r = mid - 1;
        }

        l=1, r=L;
        int p = L;
        while(l <= r) {
            int mid = (l + r) / 2;
            if(fwt.query(mid) == fwt.query(L)) p = mid, r = mid - 1;
            else l = mid + 1;
        }

        fwt.update(p, p+c-1, 1);
        if(L+c <= R) fwt.update(L+c, R, 1);
    }

    for(int i=1; i<N; i++) {
        ll x = fwt.query(i);
        ans += x * (x - 1) / 2;
    }
    cout << ans << '\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10