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>
using namespace std;
//BIT Fenwick tree
int n ;
int bit[10001]={0};
void add(int e,int v){
while(e<=n){
bit[e]+=v;
e+=e&-e;
}
}
long long sum(int e){
long long res = 0;
while(e>=1){
res+=bit[e];
e -= e&-e;
}
return res;
}
//end BIT
long long k;
vector<pair<long long,long long>> arr(42);
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>k;
set<long long> s;
for(int i = 0;i<n;i++){
long long a,b;cin>>a>>b;
s.insert(a);
arr[i] = {a,b};
}
map<long long,long long> compress;
int z =0;
for(auto i:s){
compress[i] = ++z;
}
for(int i = 0;i<n;i++){
arr[i].first = compress[arr[i].first];
}
arr[40]={0,0};
long long ans = 0;
if(n<=20){
for(long long mask=1;mask<(1<<n);mask++){
long long s=0,p=40;
for(long long i=0;i<n;i++){
if((1<<i)&mask){
if(arr[i].first>=arr[p].first){
s+=arr[i].second;
}
else{
s=-1;
break;
}
p=i;
}
}
if(s>=k)ans++;
}
}else{
vector<pair<long long,long long>> v,w;
for(long long mask=1;mask<(1<<20);mask++){
long long s=0,p=40;
for(long long i=0;i<20;i++){
if((1<<i)&mask){
if(arr[i].first>=arr[p].first){
s+=arr[i].second;
}
else{
s=-1;
break;
}
p=i;
}
}
if(s>=k)ans++;
if(s!=-1)v.push_back({s,arr[p].first});
}
vector<pair<long long,long long>> cd;
for(int i = 20;i<n;i++){
cd.push_back({arr[i].first,arr[i].second});
}
n-=20;
for(long long mask=1;mask<(1<<n);mask++){
long long s=0,p=40;
for(long long i=0;i<n;i++){
if((1<<i)&mask){
if(cd[i].first>=cd[p].first){
s+=cd[i].second;
}
else{
s=-1;
break;
}
p=i;
}
}
if(s>=k)ans++;
w.push_back({s,arr[p].first});
}
sort(w.begin(),w.end());
int e = v.size()-1;
for(int i = 0;i<w.size();i++){
while(e>=0&&v[e].first+w[i].first>=k){add(v[e].second,1);e--;}
ans+=sum(w[i].second);
}
}
cout<<ans;
return 0;
}
Compilation message (stderr)
san.cpp: In function 'int main()':
san.cpp:102:24: 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]
102 | for(int i = 0;i<w.size();i++){
| ~^~~~~~~~~
# | 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... |