답안 #720261

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
720261 2023-04-07T18:58:41 Z urosk Sails (IOI07_sails) C++14
0 / 100
338 ms 6568 KB
    #define here cerr<<"===========================================\n"
    #define dbg(x) cerr<<#x<<": "<<x<<endl;
    #include "bits/stdc++.h"
    //#include <ext/pb_ds/tree_policy.hpp>
    //#include <ext/pb_ds/assoc_container.hpp>
    #define ld double
    #define ll long long
    #define llinf 100000000000000000LL // 10^17
    #define pb push_back
    #define popb pop_back
    #define fi first
    #define sc second
    #define endl '\n'
    #define pll pair<ll,ll>
    #define pld pair<ld,ld>
    #define all(a) a.begin(),a.end()
    #define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
    #define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}
     
    #define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
     
    using namespace std;
    //using namespace __gnu_pbds;
    /*
    ll add(ll x,ll y){
        x+=y;
        if(x<0){
            x%=mod;
            x+=mod;
        }else{
            if(x>=mod) x%=mod;
        }
        return x;
    }
    ll mul(ll a,ll b){
    	ll ans = (a*b)%mod;
    	if(ans<0) ans+=mod;
    	return ans;
    }
    typedef tree<int,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
    typedef tree<int,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    ll rnd(ll l,ll r){
        return uniform_int_distribution<ll>(l,r)(rng);
    }
    */
    #define maxn 100005
    ll n,q;
    pll a[maxn];
    ll t[2*maxn],ls[2*maxn],rs[2*maxn],tsz = 0,root = 0;
    void init(ll &v,ll tl,ll tr){
        if(!v) v = ++tsz;
        if(tl==tr) return;
        ll mid = (tl+tr)/2;
        init(ls[v],tl,mid);
        init(rs[v],mid+1,tr);
    }
    void upd(ll v,ll tl,ll tr,ll l,ll r,ll x){
        if(l>r||tl>r||l>tr||tl>tr) return;
        if(tl>=l&&tr<=r){t[v]+=x;return;}
        ll mid = (tl+tr)/2;
        upd(ls[v],tl,mid,l,r,x);
        upd(rs[v],mid+1,tr,l,r,x);
    }
    ll get(ll v,ll tl,ll tr,ll i){
        if(tl==tr) return t[v];
        ll mid = (tl+tr)/2;
        if(i<=mid) return t[v] + get(ls[v],tl,mid,i);
        return t[v] + get(rs[v],mid+1,tr,i);
    }
     
    ll mx = 100000;
    void tc(){
        cin >> n;
        for(ll i = 1;i<=n;i++) cin >> a[i].fi >> a[i].sc;
        sort(a+1,a+1+n);
        reverse(a+1,a+1+n);
        init(root,1,mx);
        for(ll i = 1;i<=n;i++){
            ll h = a[i].fi,c = a[i].sc;
            ll tl = 1,tr = c;
            ll val = get(1,1,mx,tr);
            if(tr==n||get(1,1,mx,tr)!=get(1,1,mx,tr+1)){
                upd(1,1,mx,tl,tr,1);
                continue;
            }
            ll tl2 = tr,tr2 = tr;
            for(ll j = 19;j>=0;j--){
                if(tl2-(1<<j)>=1&&get(1,1,n,tl2-(1<<j))==val) tl2-=(1<<j);
                if(tr2+(1<<j)<=h&&get(1,1,n,tr2+(1<<j))==val) tr2+=(1<<j);
            }
            upd(1,1,mx,tl,tl2-1,1);
            upd(1,1,mx,tr2-(c-(tl2-tl))+1,tr2,1);
        }
        ll ans = 0;
        for(ll i = 1;i<=mx;i++){
            ll x = get(1,1,mx,i);
            ans+=x*(x-1)/2;
        }
        cout<<ans<<endl;
    }
    int main(){
    	daj_mi_malo_vremena
        int t; t = 1;
        while(t--){
            tc();
        }
    	return 0;
    }
    /**
    6
    3 2
    5 3
    4 1
    2 1
    4 3
    3 2
    **/
# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 3412 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 3412 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 3412 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 3472 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 3540 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 19 ms 3876 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 46 ms 4464 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 115 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 229 ms 6184 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 208 ms 6328 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 338 ms 6568 KB Output isn't correct
2 Halted 0 ms 0 KB -