제출 #1337186

#제출 시각아이디문제언어결과실행 시간메모리
1337186khanhphucscratchSails (IOI07_sails)C++20
100 / 100
258 ms12064 KiB
#include<bits/stdc++.h>
using namespace std;
const long long lim = 1e10;
struct Node
{
    long long sum = 0, len = 0;
    int lazy = 0, lc, rc;
    Node(long long sum, long long len, int lazy, int lc, int rc): sum(sum), len(len), lazy(lazy), lc(lc), rc(rc){}
};
void combine(Node &ans, Node &a, Node &b)
{
    ans.sum = a.sum + b.sum + a.len*a.lazy + b.len*b.lazy;
}
vector<Node> st;
void pushdown(int node)
{
    if(st[node].lc == -1){
        st[node].lc = st.size(); st.emplace_back(0, (st[node].len+1)/2, 0, -1, -1);
    }
    st[st[node].lc].lazy += st[node].lazy;
    if(st[node].rc == -1){
        st[node].rc = st.size(); st.emplace_back(0, st[node].len/2, 0, -1, -1);
    }
    st[st[node].rc].lazy += st[node].lazy; st[node].lazy = 0;
}
void range_update(int node, long long l, long long r, long long tl, long long tr, long long val)
{
    if(l > tr || r < tl) return;
    if(l >= tl && r <= tr) st[node].lazy += val;
    else{
        pushdown(node);
        long long mid = (l+r)/2;
        range_update(st[node].lc, l, mid, tl, tr, val);
        range_update(st[node].rc, mid+1, r, tl, tr, val);
        combine(st[node], st[st[node].lc], st[st[node].rc]);
    }
}
long long range_query(int node, long long l, long long r, long long tl, long long tr)
{
    if(l > tr || r < tl) return 0;
    if(l >= tl && r <= tr){
        return st[node].sum + st[node].len * st[node].lazy;
    }
    else{
        pushdown(node);
        long long mid = (l+r)/2;
        long long ans = range_query(st[node].lc, l, mid, tl, tr);
        ans += range_query(st[node].rc, mid+1, r, tl, tr);
        combine(st[node], st[st[node].lc], st[st[node].rc]);
        return ans;
    }
}
multiset<long long> mst;
vector<int> add_order, erase_order;
void update(long long l, long long r, long long val)
{
    //cerr<<"B"<<l<<" "<<r<<" "<<val<<endl;
    for(int i = 1; i <= val; i++){
        add_order.push_back(r+1);
        if(l > 1) erase_order.push_back(l);
    }
    range_update(0, 1, lim, l, r, val);
}
int main()
{
    st.emplace_back(0, lim, 0, -1, -1);
    /*
    range_update(0, 1, lim, 2, 3, 1);
    range_update(0, 1, lim, 4, 4, 1);
    range_update(0, 1, lim, 3, 4, 1);
    cout<<range_query(0, 1, lim, 3, 5)<<endl;
    return 0;
    */
    int n; cin>>n;
    vector<pair<int, int>> a(n);
    for(int i = 0; i < n; i++) cin>>a[i].first>>a[i].second;
    sort(a.begin(), a.end()); mst.insert(1); mst.insert(lim+1);
    long long ans = 0, m = 0;
    for(int i = 0; i < n; i++){
        //Add some elements
        m = a[i].first;
        //Query the sum of the last elements
        long long add = range_query(0, 1, lim, m-a[i].second+1, m);
        //cerr<<"C"<<m-a[i].second+1<<" "<<m<<" "<<add<<endl;
        ans += add;
        //Add
        long long num = a[i].second;
        multiset<long long>::iterator it = mst.lower_bound(m-num+1);
        if((*it) > m){
            it--;
            update(*it, (*it)+num-1, 1);
        }
        else{
            update(*it, m, 1); num -= m-(*it)+1;
            if(num > 0){
                //cerr<<"A"<<(*it)<<endl;
                it--;
                update(*it, (*it)+num-1, 1);
            }
        }
        for(auto j : add_order) mst.insert(j);
        for(auto j : erase_order) mst.erase(mst.lower_bound(j));
        add_order.clear(); erase_order.clear();
        //for(auto i : mst) cerr<<i<<" ";
        //cerr<<endl;
    }
    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...