#include <bits/stdc++.h>
#define endl "\n"
typedef long long ll;
using namespace std;
const ll N = 1048580 ;
const ll mod = 1e9+7;
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 < seg[x].size() && j < 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 < seg[x].size()){
ret.push_back(seg[x][i]) ;
i++ ;
}
while(j < 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 < x1.size() && j < 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 < x1.size()){
ret.push_back(x1[i]) ;
i++ ;
}
while(j < 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 < 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 < 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() , k - v1[i].second) - v.begin() ;
int sum = v.size() - q + 1 ;
ans += sum ;
}
}
cout << ans << endl ;
return 0;
}
Compilation message
san.cpp: In function 'std::vector<int> mer(int, int)':
san.cpp:15:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
15 | while(i < seg[x].size() && j < seg[x2].size()){
| ~~^~~~~~~~~~~~~~~
san.cpp:15:34: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
15 | while(i < seg[x].size() && j < seg[x2].size()){
| ~~^~~~~~~~~~~~~~~~
san.cpp:29:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | while(i < seg[x].size()){
| ~~^~~~~~~~~~~~~~~
san.cpp:33:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | while(j < seg[x2].size()){
| ~~^~~~~~~~~~~~~~~~
san.cpp: In function 'std::vector<int> get(int, int, int, int, int)':
san.cpp:60:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | while(i < x1.size() && j < x2.size()){
| ~~^~~~~~~~~~~
san.cpp:60:30: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | while(i < x1.size() && j < x2.size()){
| ~~^~~~~~~~~~~
san.cpp:74:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | while(i < x1.size()){
| ~~^~~~~~~~~~~
san.cpp:78:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | while(j < x2.size()){
| ~~^~~~~~~~~~~
san.cpp: In function 'int main()':
san.cpp:145:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
145 | for(int i = 0 ; i < v2.size() ; i++){
| ~~^~~~~~~~~~~
san.cpp:156:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
156 | for(ll i = 0 ; i < v1.size() ; i++){
| ~~^~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
37 ms |
65540 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
30 ms |
65540 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
31 ms |
65540 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
31 ms |
65540 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
32 ms |
65540 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
