제출 #1355910

#제출 시각아이디문제언어결과실행 시간메모리
1355910waygonzSails (IOI07_sails)C++20
100 / 100
56 ms1604 KiB
#include <bits/stdc++.h>
#define L long long

using namespace std;

const int H = (int)1e5;

struct FenwickTree {
    int N;
    vector<int> fw;
    void update(int x, int v) {
        while (x <= N) fw[x] += v, x += x & -x;
    }
    void range_update(int l, int r, int v) {
        if (l > r) return;
        update(l, v);
        update(r+1, -v);
    }
    int query(int x) {
        int res = 0;
        while (x > 0) res += fw[x], x -= x & -x;
        return res;
    }
    int low(int x, int l, int r) {
        r++;
        while (l < r) {
            int mid = (l + r) / 2;
            if (query(mid) <= x) r = mid;
            else l = mid + 1;
        }
        return l;
    }
    int high(int x, int l, int r) {
        l--;
        while (l < r) {
            int mid = (l + r + 1) / 2;
            if (query(mid) >= x) l = mid;
            else r = mid - 1;
        }
        return l;
    }
} T;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    T.N = H, T.fw.assign(H+1, 0);
    vector<pair<int, int>> a(n+1);
    for (int i = 1; i <= n; i++) cin >> a[i].first >> a[i].second;
    sort(a.begin() + 1, a.end());
    for (int i = 1; i <= n; i++) {
        int x = T.query(a[i].first - a[i].second + 1);
        int l = T.high(x, 1, a[i].first) + 1, r = a[i].first;
        T.range_update(l, r, 1);
        int ll = T.low(x, 1, a[i].first);
        int rr = ll + a[i].second - r + l - 2;
        T.range_update(ll, rr, 1);
    }
    L ans = 0;
    for (int i = 1; i <= H; i++) ans += (L)T.query(i) * (L)(T.query(i) - 1) / 2;
    cout << ans;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…