Submission #157773

#	Time	Username	Problem	Language	Result	Execution time	Memory
157773		Nucleist	Simfonija (COCI19_simfonija)	C++14	11 / 110	1080 ms	12268 KiB

simfonija

#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 (stderr)

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)
                  ~~^~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 11
• Subtask 5: 0 / 11
• Subtask 6: 0 / 11
• Subtask 7: 0 / 11
• Subtask 8: 0 / 11
• Subtask 9: 0 / 11
• Subtask 10: 0 / 11