제출 #1354072

#제출 시각아이디문제언어결과실행 시간메모리
1354072njoopSails (IOI07_sails)C++20
60 / 100
464 ms8816 KiB
#include <bits/stdc++.h>
#define int long long
using namespace std;

struct sgt {
    int n;
    vector<int> seg, lazy;

    void init(int sz) {
        n = sz;
        seg.assign(4*n+10, 0);
        lazy.assign(4*n+10, 0);
    }

    void push(int l, int r, int node) {
        if(lazy[node] == 0) return;
        seg[node] += (r-l+1)*lazy[node];
        if(l != r) {
            lazy[node*2+1] += lazy[node];
            lazy[node*2+2] += lazy[node];
        }
        lazy[node] = 0;
    }

    void update(int l, int r, int idl, int idr, int val, int node) {
        push(l, r, node);
        if(l > idr || r < idl) return;
        if(idl <= l && r <= idr) {
            lazy[node] += val;
            push(l, r, node);
            return;
        }
        int mid = (l+r)/2;
        update(l, mid, idl, idr, val, node*2+1);
        update(mid+1, r, idl ,idr, val, node*2+2);
        seg[node] = seg[node*2+1] + seg[node*2+2];
    }

    int query(int l, int r, int ql, int qr, int node) {
        push(l, r, node);
        if(l > qr || r < ql) return 0;
        if(l >= ql && r <= qr) return seg[node];
        int mid = (l+r)/2;
        return query(l, mid, ql, qr, node*2+1) + query(mid+1, r, ql, qr, node*2+2);
    }

    void upd(int idl, int idr, int val) {
        update(0, n, idl, idr, val, 0);
    }

    int qry(int ql, int qr) {
        return query(0, n, ql, qr, 0);
    }
};

sgt seg;

int ubound(int val, int range) {
    int l=1, r=range;
    if(val > seg.qry(1, 1)) return -1;
    while(l < r) {
        int mid = (l+r)/2;
        if(seg.qry(mid, mid) >= val) l = mid;
        else r = mid-1;
    }
    return l;
}

int lbound(int val, int range) {
    int l=1, r=range;
    if(val < seg.qry(range, range)) return -1;
    while(l < r) {
        int mid = (l+r)/2;
        if(seg.qry(mid, mid) > val) l = mid+1;
        else r = mid;
    }
    return l;
}

signed main() {
    int n, ans=0;
    cin >> n;
    seg.init(n);
    vector<pair<int, int>> v;
    for(int i=1; i<=n; i++) {
        int h, sa;
        cin >> h >> sa;
        v.push_back({h, sa});
    }
    sort(v.begin(), v.end());
    for(auto i: v) {
        int h = i.first, sa = i.second;
        int val = seg.qry(h-sa+1, h-sa+1);
        if(val > seg.qry(h, h)) {
            int l = h, r = lbound(val-1, h);
            sa -= l-r+1;
            seg.upd(r, l, 1);
        }
        int l = lbound(val, h);
        seg.upd(l, l+sa-1, 1);
    }
    for(int i=1; i<=n; i++) {
        int t = seg.qry(i, i);
        ans += t*(t-1)/2;
    }
    cout << ans;
}
#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...