Submission #522923

#	Time	Username	Problem	Language	Result	Execution time	Memory
522923		ali22413836	San (COCI17_san)	C++14	0 / 120	36 ms	65540 KiB

san

#include <bits/stdc++.h>
#define endl "\n"
typedef long long ll ;
using namespace std ;
const ll N = 1048580 ;
int a[48] , b[48] , n ;
ll k ;
vector < int > seg[4*N] ;
int sec[1048580] ;
vector < pair < ll , int > > v1 , v2 ;
vector < int > mer(int x , int x2){
    ll i = 0 , j = 0 ;
    vector < int > ret ;
    while(i < (int)seg[x].size() && j < (int)seg[x2].size()){
        if(seg[x][i] == 0)
            i++ ;
        if(seg[x2][j] == 0)
            j++ ;
        if(seg[x][i] < seg[x2][j]){
            ret.push_back(seg[x][i]) ;
            i++ ;
        }
        else{
            ret.push_back(seg[x2][j]) ;
            j++ ;
        }
    }
    while(i < (int)seg[x].size()){
        ret.push_back(seg[x][i]) ;
        i++ ;
    }
    while(j < (int)seg[x2].size()){
        ret.push_back(seg[x2][j]) ;
        j++ ;
    }
    return ret ;
}
void build(int x , int lx , int rx){
    if(lx == rx){
        seg[x].push_back(sec[lx]) ;
        return ;
    }
    ll mid = (lx + rx) / 2 ;
    build(x * 2 , lx , mid) , build(x * 2 + 1 , mid + 1 , rx) ;
    seg[x] = mer(x * 2 , x * 2 + 1) ;
    return ;
}
vector < int > get(int l , int r , int x , int lx , int rx){
    if(lx > rx || rx < l){
        return {0} ;
    }
    if(l <= lx && rx <= r){
        return seg[x] ;
    }
    ll mid = (lx + rx) / 2 ;
    vector < int > x1 = get(l , r , x * 2 , lx , mid), x2 = get(l , r , x * 2 , mid + 1 , rx) ;
    ll i = 0 , j = 0 ;
    vector < int > ret ;
    while(i < (int)x1.size() && j < (int)x2.size()){
        if(x1[i] == 0)
            i++ ;
        if(x2[j] == 0)
            j++ ;
        if(x1[i] < x2[j]){
            ret.push_back(x1[i]) ;
            i++ ;
        }
        else{
            ret.push_back(x2[j]) ;
            j++ ;
        }
    }
    while(i < (int)x1.size()){
        ret.push_back(x1[i]) ;
        i++ ;
    }
    while(j < (int)x2.size()){
        ret.push_back(x2[j]) ;
        j++ ;
    }
    return ret ;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> k ;
    for(int i = 0 ; i < n ;i++){
    cin >> a[i] >> b[i] ;
    }
    int ind = 1 ;
    ll ans = 0 ;
    for(int i = 0 ; i < (1 << min(n , 20)) ; i++){
        int mx = 0 ;
        ll cur = 0 ;
        // cout << i << endl ;
        for(int j = 0 ; j < min(n , 20) ; j++){
            if((i & (1ll << j))){
                if(a[j] >= mx){
                    // cout << j << " " ;
                    cur += b[j] ;
                }
                else{
                    cur = -1e18 ;
                    break ;
                }
                mx = max(a[j] , mx) ;
            }
        }
        // cout << endl ;
        // cout << cur << endl ;
        if(cur != -1e18){
            v1.push_back({cur , mx}) ;
        }
    }
    n -= 20 ;
    n = max(n , 0);
    if(n != 0){
        for(int i = 0 ; i < (1 << min(n , 20)) ; i++){
            int mx = 0 ;
            ll cur = 0 ;
            int fi = -1 ;
            // cout << i << endl ;
            for(int j = 20 ; j < n ; j++){
                int q = j - 20 ;
                if((i & (1 << q))){
                    if(fi == -1)
                        fi = a[j] ;
                    if(a[j] >= mx){
                        // cout << j << " " ;
                        cur += b[j] ;
                    }
                    else{
                        cur = -1e18 ;
                        break ;
                    }
                }
            }
            // cout << endl ;
            // cout << cur << endl ;
            if(cur != -1e18 && fi != -1){
               v2.push_back({cur , fi}) ;
            }
        }
        sort(v2.begin() , v2.end()) ;
        for(int i = 0 ; i < (int)v2.size() ; i++){
            sec[ind] = v2[i].second;
            ind++ ;
        }
        ind-- ;
        if(ind > 0)
            build(1 , 1 , ind) ;
    }
    else{
        ind = 0;
    }
    for(ll i = 0 ; i < (int)v1.size() ; i++){
        if(v1[i].first >= k){
            ans++ ;
        }
        ll need = k - v1[i].first ;
        if(ind != 0){
            int l = 0 , r = ind + 1 ;
            while(r - l > 0){
                ll mid = (l + r) / 2 ;
                if(v2[mid].first >= need){
                    r = mid ;
                }
                else{
                    l = mid ;
                }
            }
            if(r == ind + 1)
                continue ;
            vector < int > v = get(r , ind , 1 , 1 , ind) ;
            int q = lower_bound(v.begin() , v.end() , v1[i].second) - v.begin() ;
            int sum = v.size() - q + 1 ;
            ans += sum ;
        }
    }
    cout << ans << endl ;
    return 0;
}

• Subtask 1: 0 / 24
• Subtask 2: 0 / 24
• Subtask 3: 0 / 24
• Subtask 4: 0 / 24
• Subtask 5: 0 / 24