#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 rec_left(int pos, int last, ll sum) {
if (pos == n/2) {
int idx = lower_bound(hs.begin(), hs.end(), last) - hs.begin();
L[idx].push_back(sum);
return;
}
rec_left(pos+1, last, sum);
if (h[pos] >= last) {
rec_left(pos+1, h[pos], sum + c[pos]);
}
}
void rec_right(int pos, int first, int last, ll sum) {
if (pos == n) {
int idx = lower_bound(hs.begin(), hs.end(), first) - hs.begin();
R[idx].push_back(sum);
return;
}
rec_right(pos+1, first, last, sum);
if (h[pos] >= last) {
int nfirst = (first == 0) ? h[pos] : first;
rec_right(pos+1, nfirst, h[pos], sum + c[pos]);
}
}
void left( int pos, int currH, ll 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, ll 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);
/*
rec_left( 0, 0, 0 );
rec_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<(int)hs.size() ; i++ ) std::sort( R[i].begin(), R[i].end() );
ll nas = 0;
for( int i=0 ; i<(int)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<(int)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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
47188 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
47240 KB |
Output is correct |
| 2 |
Incorrect |
22 ms |
47316 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
48188 KB |
Output is correct |
| 2 |
Correct |
23 ms |
47316 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
49004 KB |
Output is correct |
| 2 |
Correct |
31 ms |
47500 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
136 ms |
54568 KB |
Output is correct |
| 2 |
Correct |
39 ms |
48704 KB |
Output is correct |
