#include <algorithm>
#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int MAX_N = 1e6;
const int INF = 1e9;
const int mod = 1e9 + 7;
int n, k;
std::vector<ll> L[MAX_N];
std::vector<ll> R[MAX_N];
ll h[MAX_N];
ll c[MAX_N];
std::vector<int> hs;
void left( int pos, int currH, int sum ){
if( pos == n/2 ){
int ind = std::lower_bound( hs.begin(), hs.end(), currH ) - hs.begin();
L[ind].push_back(sum);
return;
}
left( pos +1, currH, sum );
if( currH <= h[pos] ){
left( pos +1, h[pos], sum + c[pos] );
}
}
void right( int pos, int first, int currH, int sum ){
if( pos == n ){
int ind = std::lower_bound( hs.begin(), hs.end(), first ) - hs.begin();
R[ind].push_back( sum );
return ;
}
right( pos +1, first, currH, sum );
if( h[pos] >= currH ){
if( first == 0 ) first = h[pos];
right( pos +1, first, h[pos], sum + c[pos] );
}
}
int main () {
std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);
std::cin>>n>>k;
for( int i=0 ; i<n ; i++ ){
std::cin>>h[i]>>c[i];
hs.push_back( h[i] );
}
hs.push_back(0);
std::sort( hs.begin(), hs.end() );
left( 0, 0, 0 );
right(n/2, 0, 0, 0);
/*
std::cerr<<" L:\n";
for( int i=0 ; i<n ; i++ ){
std::cerr<<i<<" : ";
for( auto j : L[i] ){
std::cerr<<j<<" ";
}
std::cerr<<"\n";
}
std::cerr<<" R:\n";
for( int i=0 ; i<n ; i++ ){
std::cerr<<i<<" : ";
for( auto j : R[i] ){
std::cerr<<j<<" ";
}
std::cerr<<"\n";
}
*/
for( int i=0 ; i<hs.size() ; i++ ) std::sort( R[i].begin(), R[i].end() );
ll nas;
for( int i=0 ; i<hs.size(); i++ ){
// std::cerr<<i<<":\n";
for( auto it : L[i] ){
nas += R[0].end() - std::lower_bound( R[0].begin(), R[0].end(), k - it );
// std::cerr<<" "<<it<<"\n";
for( int j=i ; j<hs.size() ; j++ ){
ll currNas = R[j].end() - std::lower_bound( R[j].begin(), R[j].end(), k-it );
// std::cerr<<" # "<<j<<" "<<currNas<<"\n";
nas += currNas;
}
}
}
std::cout<<nas<<"\n";
return 0;
}
Compilation message
san.cpp: In function 'int main()':
san.cpp:83:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | for( int i=0 ; i<hs.size() ; i++ ) std::sort( R[i].begin(), R[i].end() );
| ~^~~~~~~~~~
san.cpp:86:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for( int i=0 ; i<hs.size(); i++ ){
| ~^~~~~~~~~~
san.cpp:92:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | for( int j=i ; j<hs.size() ; j++ ){
| ~^~~~~~~~~~
san.cpp:90:8: warning: 'nas' may be used uninitialized in this function [-Wmaybe-uninitialized]
90 | nas += R[0].end() - std::lower_bound( R[0].begin(), R[0].end(), k - it );
| ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
47188 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
47316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
48204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
48904 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
325 ms |
54576 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
