Submission #522814

#TimeUsernameProblemLanguageResultExecution timeMemory
522814ali22413836San (COCI17_san)C++14
Compilation error
0 ms0 KiB
#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[48] , b[48] , 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 ind = 1 ; 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); if(n != 0){ 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 = 20 ; 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()) ; 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 (stderr)

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 'void build(ll, ll, ll)':
san.cpp:40:9: error: 'seg' was not declared in this scope
   40 |         seg[x].push_back(sec[lx]) ;
      |         ^~~
san.cpp:40:26: error: 'sec' was not declared in this scope
   40 |         seg[x].push_back(sec[lx]) ;
      |                          ^~~
san.cpp:45:5: error: 'seg' was not declared in this scope
   45 |     seg[x] = mer(seg[x * 2] , seg[x * 2 + 1]) ;
      |     ^~~
san.cpp: In function 'std::vector<long long int> get(ll, ll, ll, ll, ll)':
san.cpp:53:16: error: 'seg' was not declared in this scope
   53 |         return seg[x] ;
      |                ^~~
san.cpp: In function 'int main()':
san.cpp:119:27: 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]
  119 |         for(int i = 0 ; i < v2.size() ; i++){
      |                         ~~^~~~~~~~~~~
san.cpp:120:13: error: 'sec' was not declared in this scope
  120 |             sec[ind] = v2[i].second;
      |             ^~~
san.cpp:127: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]
  127 |     for(int i = 0 ; i < v1.size() ; i++){
      |                     ~~^~~~~~~~~~~