#include <bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
using namespace std;
#define flash ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ll long long
#define INF 1000000000
#define pb push_back
#define ve vector<ll>
#define dos pair<ll,ll>
#define vedos vector<dos>
#define rand mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
struct greateri
{
template<class T>
bool operator()(T const &a, T const &b) const { return a > b; }
};
ll n,k;
ve hedi,hedi1;
map<ll,ll>sparse,invsparse,inu;
set<ll>diff;
ll seg[200000],bit[200000],bit2[200000];
void build(ll index,ll l,ll r)
{
if(l==r)
{
seg[index]=inu[invsparse[l]]*invsparse[l];
return;
}
//////debug(index);
ll med = (l+r)/2;
build(index*2,l,med);
build(index*2+1,med+1,r);
seg[index]=seg[index*2]+seg[index*2+1];
}
ll query(ll index,ll l,ll r,ll l1,ll r1)
{
if(l>r1 || r<l1)return 0;
else if(l>=l1 && r<=r1)return seg[index];
ll med = (l+r)/2;
return query(index*2,l,med,l1,r1)+query(index*2+1,med+1,r,l1,r1);
}
ll adjust(ll kol,ll vol,bool noi)
{
if(noi)for(;kol<=n; kol+=(kol&(-kol)))bit[kol]+=vol;
else for (;kol<=n; kol+=(kol&(-kol)))bit2[kol]+=vol;
}
ll range_add(ll l,ll r,ll val)
{
adjust(l,val,1);
adjust(r+1,-val,1);
adjust(l,val*(l-1),0);
adjust(r+1,-val*r,0);
}
ll sum(ll b,ll index)
{
ll total=0;
if(b)
{
while(index>0)
{
//////debug(index);
total+=bit[index];
index-=(index&(-index));
}
}
else
{
while(index>0)
{
total+=bit2[index];
index-=(index&(-index));
}
}
return total;
}
ll prefix(ll index)
{
return sum(1,index)*index-sum(0,index);
}
ll range_query(ll l,ll r)
{
////debugs(l,r);
return prefix(r)-prefix(l-1);
}
int main()
{
flash;
cin>>n>>k;
for (ll i = 0; i < n; ++i)
{
ll yo;cin>>yo;hedi.pb(yo);
}
for (ll i = 0; i < n; ++i)
{
ll yo;cin>>yo;hedi1.pb(yo);
}
ll initial=0;
vedos fayi1;
ve fayi;
for (ll i = 0; i < n; ++i)
{
fayi1.pb({abs(hedi1[i]-hedi[i]),hedi1[i]-hedi[i]});
}
sort(fayi1.begin(),fayi1.end(),greater<pair<ll,ll>>());
for (ll i = k; i < n; ++i)
{
//////debug(fayi1[i].second);
fayi.pb(fayi1[i].second);
}
sort(fayi.begin(),fayi.end());
if(fayi.size()==0)
{
cout<<0;return 0;
}
for (ll i = 0; i < fayi.size(); ++i)
{
diff.insert(fayi[i]);
inu[fayi[i]]++;
initial+=(abs(fayi[i]));
}
ll index=1;
for(auto it:diff)
{
invsparse[index]=it;
sparse[it]=index;
//////debug(it);
range_add(index,index,inu[it]);
index++;
}
build(1,1,index-1);
ll ans = initial;
for (ll i = 1000001; i > -1000001; --i)
{
ll cur = initial;
if(i>=0)
{
bool ki = true;
auto ka = diff.upper_bound(-i);
if((*ka)>=0 || ka==diff.end())ki=false;
auto zo = sparse[(*ka)];
auto ka1 = diff.lower_bound(0);
if(ka1==diff.begin())ki=false;
ka1--;
auto doi = sparse[(*ka1)];
if(doi<zo || (*ka1)>=0)ki=false;
if(ki)
{
cur-= query(1,1,index-1,zo,doi);
cur+=((query(1,1,index-1,zo,doi))+(i*(range_query(zo,doi))));
}
if(ka!=diff.begin())
{ka--;
doi = sparse[(*ka)];
cur-=(range_query(1,doi))*i;}
ka1++;
if(ka1!=diff.end())
cur+=(range_query(sparse[(*ka1)],index-1))*i;
}
else
{
bool ki = true;
auto ka = diff.lower_bound(-i);
if(ka==diff.begin())ki=false;
if(ka==diff.end())ka--;
if(ka!=diff.begin())ka--;
//debug(*ka);
auto zo = sparse[(*ka)];
auto ka1 = diff.upper_bound(0);
if(ka1==diff.end())ki=false;
auto doi = sparse[(*ka1)];
//debug(ki);
//debugs(doi,zo);
if(ki && doi<=zo)
{
cur-= query(1,1,index-1,doi,zo);
cur+=abs(((query(1,1,index-1,doi,zo))+(i*(range_query(doi,zo)))));
}
//debug(cur);
if(ka1!=diff.begin())
{ka1--;
doi = sparse[(*ka1)];
cur-=(range_query(1,doi))*i;}
if(ka!=diff.end() && ki)ka++;
////debug((*ka));
if(ka!=diff.end())
cur+=(range_query(sparse[(*ka)],index-1))*i;
//debugs(cur,1);
}
ans=min(cur,ans);
}
cout<<ans;
return 0;
}
//code the AC sol !
// BS/queue/map
Compilation message
simfonija.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
#pragma GCC optimization ("O3")
simfonija.cpp:4:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
#pragma GCC optimization ("unroll-loops")
simfonija.cpp: In function 'long long int adjust(long long int, long long int, bool)':
simfonija.cpp:52:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
simfonija.cpp: In function 'long long int range_add(long long int, long long int, long long int)':
simfonija.cpp:59:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
simfonija.cpp: In function 'int main()':
simfonija.cpp:121:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (ll i = 0; i < fayi.size(); ++i)
~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
130 ms |
404 KB |
Output is correct |
| 2 |
Correct |
129 ms |
404 KB |
Output is correct |
| 3 |
Correct |
128 ms |
504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1069 ms |
7008 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1050 ms |
7068 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1076 ms |
7036 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
109 ms |
4080 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1080 ms |
12268 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
89 ms |
4076 KB |
Output is correct |
| 2 |
Incorrect |
278 ms |
5172 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1075 ms |
8812 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
723 ms |
4720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
283 ms |
5100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
