Submission #850514

#	Time	Username	Problem	Language	Result	Execution time	Memory
850514		Samrev	Sails (IOI07_sails)	C++14	90 / 100	414 ms	9124 KiB

sails

#include <bits/stdc++.h>
using namespace std;
#define LSOne(x) (x&(-x))
typedef long long int ll;
typedef long double ld;
ll t = 1;
const ll M = 1e9 + 7;
ll mod_add(ll a, ll b){
    return ((a%M) + (b %M))%M;
}
ll mod_mul(ll a, ll b){
    return ((a%M)*(b%M))%M;
}
const ll MAX = 1e18;

ll lcm(ll a , ll b){
    return (a*b)/__gcd(a,b);
}

struct SEGTREE
{
    vector<ll> values;
    ll sz = 1;
    SEGTREE(ll n){
        while(sz <n){
            sz *= 2;
        }
        values.assign(2*sz , 0);
    }
    void update(ll i , ll v , ll x , ll lx , ll rx){
        if((rx - lx) == 1){
            values[x] += v;
            return;
        }
        ll m = lx + (rx - lx)/2;
        if(i < m){
            update(i , v , 2*x + 1, lx , m);
        }
        else{
            update(i , v , 2*x + 2, m , rx);
        }
        values[x] = values[2*x + 1] + values[2*x + 2];
    }
    void update(ll i , ll v){
        if(i>sz) return;
        update(i , v , 0 , 0 , sz);
    }
    ll get(ll l ,ll r, ll x, ll lx , ll rx){
        if((lx >= l) &&(rx<=r)) return values[x];
        if((lx>=r) || (rx<=l)) return 0;

        ll m = lx + (rx - lx)/2;
        ll r1 = get(l , r, 2*x + 1, lx , m);
        ll r2 = get(l , r , 2*x + 2, m ,rx);
        return r1 + r2;
    }
    ll get(ll i){
        return get(0 , i+1 , 0 , 0 , sz);
    }
    ll lb(ll i , ll v){
        ll r = i, l = 0, ans = 0;
        while(l<=r){
            ll mid = l + (r - l)/2;
            ll vmid = get(mid);
            if(vmid>v){
                l = mid + 1;
            }
            else{
                ans = mid;
                r = mid - 1;
            }
        }
        return ans;
    }
    ll ub(ll left , ll right ,ll v){
        ll l = left, r = right, ans = 0;
        while(l<=r){
            ll mid = l + (r - l)/2;
            ll vmid = get(mid);
            if(vmid<v){
                r = mid - 1;
            }
            else{
                ans = mid;
                l = mid + 1;
            }
        }
        return ans;
    }
};
void solve(){
    ll n ; cin>>n;
    vector<vector<ll>> masts(n);
    for(ll i = 0 ; i<n ;i++){
        ll h , k ; cin>>h>>k;
        masts[i] = {h , k};

    }
    sort(masts.begin(),masts.end());
    ll H = masts[n-1][0];
    SEGTREE sg(H);
    
    for(int i = 0 ; i<n ; i++){
        ll idx = masts[i][0] - masts[i][1];
        ll k = masts[i][1];
        ll he = sg.get(idx);
        ll lb = sg.lb(idx , he) , ub = sg.ub(idx ,masts[i][0]-1, he);
        // cout<<ub+1<<" "<<masts[i][0]<<"\n";
        if(ub<(masts[i][0] - 1)){
            sg.update(ub + 1, 1);
            sg.update(masts[i][0], -1);
        }
        // cout<<lb<<" "<<(lb + k - (masts[i][0] - 1- ub))<<"\n";
        sg.update(lb , 1);
        sg.update(lb + k - (masts[i][0] - 1 - ub) , -1);
        // for(int i = 0;i<H;i++){
        //     cout<<sg.get(i)<<" ";
        // }
        // cout<<"\n";
    }

    ll ans = 0;
    for(int i = 0; i<H;i++){
        ll r = sg.get(i);
        ans += (r*(r -1))/2;
    }
    cout<<ans<<"\n";


    
}
    
    




int main(){

    ios::sync_with_stdio(0); cin.tie(0);
    // freopen("input.txt" , "r" , stdin);
    // freopen("output.txt" , "w", stdout);
    // cin>>t;
    while(t--){
        solve();
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 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