This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define int long long
/**
|||||||||| ||||| ||||| ||||||||||
||||||||||||| ||||| ||||| |||||
|||| |||||| ||||| ||||| |||||
||||||||||||||||| ||||||||||||||| ||||||||||
||||||||||||||||||| ||||||||||||||| |||||
||||| ||||| ||||| ||||| |||||
||||| ||||| ||||| ||||| ||||||||||
AHMED;HASSAN;SAEED;
*/
using namespace std;
int n,k;
vector<pair<int,int> >tws;
int slv(int l,int r){
vector<int>sums[2][n+1];
int n2=(r-l+1)/2;
for(int i=0;i<(1<<(n2));i++){
int sum=0;
int lst=-1;
int vld=1;
int f=n;
for(int j=0;j<30;j++){
if((1<<j)&i){
if(lst!=-1&&tws[l+j].first<tws[l+lst].first){
vld=0;
break;
}
sum+=tws[l+j].second;
lst=j;
f=l+j;
}
}
if(vld)
sums[0][f].push_back(sum);
}
n2=r-l+1-(r-l+1)/2;
for(int i=0;i<(1<<(n2));i++){
int sum=0;
int lst=-1;
int vld=1;
int f=n;
for(int j=0;j<30;j++){
if((1<<j)&i){
if(lst!=-1&&(tws[l+j+(r-l+1)/2].first<tws[l+lst+(r-l+1)/2].first)){
vld=0;
break;
}
if(lst==-1){
f=l+j+(r-l+1)/2;
}
sum+=tws[l+j+(r-l+1)/2].second;
lst=j;
}
}
if(vld)
sums[1][f].push_back(sum);
}
for(int i=0;i<n+1;i++)
sort(sums[1][i].begin(),sums[1][i].end());
int ret=0;/**
for(int i=0;i<sums[0].size();i++){
int ned=k-sums[0][i];
vector<int>::iterator it=lower_bound(sums[1].begin(),sums[1].end(),ned);
ret+=sums[1].end()-it;
}*/
for(int i=0;i<n+1;i++){
for(int j=0;j<sums[0][i].size();j++){
for(int i2=0;i2<n+1;i2++){
if(tws[i2].first<tws[i].first&&i2!=n&&i!=n)continue;
int ned=k-sums[0][i][j];
vector<int>::iterator it=lower_bound(sums[1][i2].begin(),sums[1][i2].end(),ned);
ret+=sums[1][i2].end()-it;
///cout<<i<<' '<<i2<<' '<<(sums[1][i2].end()-it)<<' '<<sums[0][i][j]<<'\n';
}
}
}
/**
///cout<<l <<' '<<r<<'\n';
///for(int j=0;j<2;j++){
for(int i=0;i<n+1;i++){
for(int j=0;j<sums[0][i].size();j++)
cout<<sums[0][i][j]<<' ';
cout<<'\n';
}
///cout<<'\n';
///}
*/
return ret;
}
int32_t main()
{
/**freopen("movie.in","r",stdin);
freopen("movie.out","w",stdout);*/
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>k;
tws=vector<pair<int,int> >(n+1,{1e11,0});
for(int i=0;i<n;i++)
cin>>tws[i].first>>tws[i].second;
cout<<slv(0,n-1)<<'\n';
return 0;
}
/**
4 3
100000000000 200000000000 300000000000 400000000000 800000000000 1000000000000 2000000000000
*/
Compilation message (stderr)
san.cpp: In function 'long long int slv(long long int, long long int)':
san.cpp:78:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for(int j=0;j<sums[0][i].size();j++){
| ~^~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |