제출 #1362942

#제출 시각아이디문제언어결과실행 시간메모리
1362942vviviSails (IOI07_sails)C++20
100 / 100
211 ms3180 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<int> st;
int m;

void add(int v, int l, int r, int tl, int tr) {
    if (l > r) return;
    if (tl == l && tr == r) {
        st[v] ++; return;
    }
    int tm = (tl + tr) / 2;
    add(v * 2, l, min(r, tm), tl, tm);
    add(v * 2 + 1, max(l, tm + 1), r, tm + 1, tr);
    return;
}

int get(int v, int tl, int tr, int pos) {
    if (tl == tr) return st[v];
    int tm = (tl + tr) / 2;
    if (pos <= tm) return st[v] + get(v * 2, tl, tm, pos);
    else return st[v] + get(v * 2 + 1, tm + 1, tr, pos);
}

bool binsearch(int mid, int x) {
    int val = get(1, 0, m - 1, mid);
    if (val >= x) return true;
    else return false;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    vector<pair<int, int>> v(n);
    for (int i = 0; i < n; i ++) cin >> v[i].first >> v[i].second;
    sort(v.begin(), v.end());
    m = v[n - 1].first;
    vector<int> db(m);
    st.resize(4 * m + 1);
    for (int i = 0; i < n; i ++) {
        int ind = v[i].first - v[i].second;
        int x = get(1, 0, m - 1, ind);
        int l = 0, r = v[i].first;
        while (l < r - 1) {
            int mid = (l + r) / 2;
            if (binsearch(mid, x)) l = mid;
            else r = mid;
        }
        add(1, r, v[i].first - 1, 0, m - 1);
        int cnt = max(0, v[i].first - r);
        l = -1, r = v[i].first - 1;
        while (l < r - 1) {
            int mid = (l + r) / 2;
            if (binsearch(mid, x + 1)) l = mid;
            else r = mid;
        }
        add(1, r, r + v[i].second - cnt - 1, 0, m - 1);
    }
    ll ans = 0;
    for (int i = 0; i < m; i ++) {
        ll c = ll(get(1, 0, m - 1, i));
        ans += c * (c - 1) / 2;
    }
    cout << ans;
    return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…