Submission #522810

# Submission time Handle Problem Language Result Execution time Memory
522810 2022-02-06T00:28:12 Z ali22413836 San (COCI17_san) C++14
0 / 120
32 ms 65540 KB
#include <bits/stdc++.h>
#define endl "\n"
typedef long long ll;
using namespace std;
const int N = 1e6+5;
const int mod = 1e9+7;
ll a[200009] , b[200009] , n , k ;
vector < ll > seg[4000009] ;
ll sec[2000009] ;
vector < pair < ll , ll > > v1 , v2 ;
vector < ll > mer(vector < ll > x , vector < ll > x2){
    ll i = 0 , j = 0 ;
    vector < ll > ret ;
    while(i < x.size() && j < x2.size()){
        if(x[i] == 0)
            i++ ;
        if(x2[j] == 0)
            j++ ;
        if(x[i] < x2[j]){
            ret.push_back(x[i]) ;
            i++ ;
        }
        else{
            ret.push_back(x2[j]) ;
            j++ ;
        }
    }
    while(i < x.size()){
        ret.push_back(x[i]) ;
        i++ ;
    }
    while(j < x2.size()){
        ret.push_back(x2[j]) ;
        j++ ;
    }
    return ret ;
}
void build(ll x , ll lx , ll 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(seg[x * 2] , seg[x * 2 + 1]) ;
    return ;
}
vector < ll > get(ll l , ll r , ll x , ll lx , ll rx){
    if(lx > rx || rx < l){
        return {0} ;
    }
    if(l <= lx && rx <= r){
        return seg[x] ;
    }
    ll mid = (lx + rx) / 2 ;
    return mer(get(l , r , x * 2 , lx , mid) , get(l , r , x * 2 + 1 , mid + 1, rx)) ;
}
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] ;
    }
    ll ans = 0 ;
    for(int i = 0 ; i < (1ll << min(n , 20ll)) ; i++){
        ll mx = 0 ;
        ll cur = 0 ;
        // cout << i << endl ;
        for(int j = 0 ; j <= min(n , 20ll) ; 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({mx , cur}) ;
        }
    }
    n -= 20 ;
    n = max(n , 0ll);
    for(int i = 0 ; i < (1ll << min(n , 20ll)) ; i++){
        ll mx = 0 ;
        ll cur = 0 ;
        ll fi = -1 ;
        // cout << i << endl ;
        for(int j = 21 ; j <= n ; j++){
            ll q = j ;
            if((i & (1ll << q))){
                if(fi == -1)
                    fi = a[j] ;
                if(a[j] >= mx){
                    // cout << j << " " ;
                    cur += b[q] ;
                }
                else{
                    cur = -1e18 ;
                    break ;
                }
            }
        }
        // cout << endl ;
        // cout << cur << endl ;
        if(cur != -1e18 && fi != -1){
           v2.push_back({fi , cur}) ;
        }
    }
    sort(v2.begin() , v2.end()) ;
    ll ind = 1 ;
    for(int i = 0 ; i < v2.size() ; i++){
        sec[ind] = v2[i].second;
        ind++ ;
    }
    ind-- ;
    if(ind != 0)
        build(1 , 1 , ind) ;
    for(int i = 0 ; i < v1.size() ; i++){
        if(v1[i].second >= k){
            ans++ ;
        }
        if(ind != 0){
            ll l = 0 , r = ind + 1 ;
            while(r - l > 0){
                ll mid = (l + r) / 2 ;
                if(v2[mid].first > v1[i].first){
                    r = mid ;
                }
                else{
                    l = mid ;
                }
            }
            if(r == ind + 1)
                continue ;
            vector < ll > v = get(r , ind , 1 , 1 , n) ;
            ll q = lower_bound(v.begin() , v.end() , k - v1[i].second) - v.begin() ;
            ll sum = v.size() - q + 1 ;
            ans += sum ;
        }
    }
    cout << ans << endl ;
    return 0;
}

Compilation message

san.cpp: In function 'std::vector<long long int> mer(std::vector<long long int>, std::vector<long long int>)':
san.cpp:14:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     while(i < x.size() && j < x2.size()){
      |           ~~^~~~~~~~~~
san.cpp:14:29: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     while(i < x.size() && j < x2.size()){
      |                           ~~^~~~~~~~~~~
san.cpp:28:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     while(i < x.size()){
      |           ~~^~~~~~~~~~
san.cpp:32:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     while(j < x2.size()){
      |           ~~^~~~~~~~~~~
san.cpp: In function 'int main()':
san.cpp:118:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |     for(int i = 0 ; i < v2.size() ; i++){
      |                     ~~^~~~~~~~~~~
san.cpp:125:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |     for(int i = 0 ; i < v1.size() ; i++){
      |                     ~~^~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 30 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 30 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 30 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -