This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// give up :((((
#include <bits/stdc++.h>
#define mp make_pair
#define f1 first
#define f2 second
#define pb push_back
#define int long long
#define pii pair<int ,int>
#define ios ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int mox=1e6+9;
vector<pii> ha,wa;
int ko[mox];
int tree[mox][2];
int n;
void add(int id , int x ,int z)
{
for(int i=id ; i<=n ; i+=(i&(-i)))
{
tree[i][z]+=x;
}
}
int get(int id , int z)
{ int ans=0;
for(int i=id ; i>0 ; i-=(i&(-i)))
{
ans+=tree[i][z];
}
return ans;
}
int32_t main()
{
ios
int k;
cin>>n>>k;
for(int i=0 ; i<n ; i++)
{
int a,b;
cin>>b>>a;
ha.pb({a,i});
wa.pb({b,i});
}
sort(ha.begin(),ha.end());
sort(wa.begin(),wa.end());
int ans=1e12;
for(int i=0 ; i<n ; i++)
{
ko[wa[i].f2]=i;
}
for(int i=0 ; i<n ; i++)
{
add(ko[ha[i].f2]+1,wa[ko[ha[i].f2]].f1,0);
add(ko[ha[i].f2]+1,1,1);
int low=0;
int hi=n+1;
while(low<hi-1)
{
int mid=(low+hi)/2;
if(get(mid,1)>=k)
{
hi=mid;
}
else
low=mid;
}
if(hi!=n+1)
{
ans=min(ans,get(hi,0)*ha[i].f1);
}
}
cout<<ans;
}
# | 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... |
# | 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... |