Submission #340500

#	Time	Username	Problem	Language	Result	Execution time	Memory
340500		ogibogi2004	Radio (Balkan15_RADIO)	C++14	100 / 100	1110 ms	47340 KiB

radio

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=1e5+6;
const ll INF=2e15;
struct event
{
	ll pos;
	bool f;
};
struct tower
{
	ll l,r;
	ll s,pos;
	bool operator<(tower const& other)const
	{
		if(s-r!=other.s-other.r)return s-r<other.s-other.r;
		else return pos<other.pos;
	}
}t[MAXN];
///change cmp functions then do "xd"
bool cmpl(tower t1,tower t2)
{
	if(t1.s-t1.r!=t2.s-t2.r)return t1.s-t1.r<t2.s-t2.r;
	return t1.pos<t2.pos;
}
bool cmpr(tower t1,tower t2)
{
	if(t1.s+t1.l!=t2.s+t2.l)return t1.s+t1.l<t2.s+t2.l;
	return t1.pos<t2.pos;
}
bool cmpm(tower t1,tower t2)
{
	if(t1.s!=t2.s)return t1.s<t2.s;
	return t1.pos<t2.pos;
}
string status[MAXN];
set<tower,decltype(cmpl)*>LeftActive(cmpl);
set<tower,decltype(cmpr)*>RightActive(cmpr);
set<tower,decltype(cmpm)*>MiddleActive(cmpm);
set<tower,decltype(cmpl)*>LeftUnactive(cmpl);
set<tower,decltype(cmpr)*>RightUnactive(cmpr);
set<tower,decltype(cmpm)*>MiddleUnactive(cmpm);
map<ll,vector<event> >sweep_line;
int main()
{
	ll n,k;
	cin>>n>>k;
	for(ll i=1;i<=n;i++)
	{
		ll x,p,s;
		cin>>x>>p>>s;
		t[i].l=x-p;
		t[i].r=x+p;
		t[i].s=s;
		t[i].pos=i;
		if(!sweep_line.count(x))
		{
			sweep_line[x]={};
		}
		sweep_line[t[i].l].push_back({i,1});
		sweep_line[t[i].r].push_back({i,0});
		RightUnactive.insert(t[i]);
		status[i]="RU";
	}
	ll total_win=0,ans=-INF,last=-INF;
	for(ll i=1;i<=n;i++)total_win+=t[i].s;
	for(auto line:sweep_line)
	{
		total_win-=(LeftActive.size()-RightActive.size())*(line.first-last);
		//cout<<line.first<<":\n";
		vector<tower>v0,v1;
		for(auto l:line.second)
		{
			if(l.f==0)v0.push_back(t[l.pos]);
			else v1.push_back(t[l.pos]);
		}
		//cout<<"*1*\n";
		for(auto v:v1)
		{
			if(status[v.pos]=="RU")
			{
				RightUnactive.erase(t[v.pos]);
				MiddleUnactive.insert(t[v.pos]);
				status[v.pos]="MU";
			}
			else if(status[v.pos]=="RA")
			{
				RightActive.erase(t[v.pos]);
				MiddleActive.insert(t[v.pos]);
				status[v.pos]="MA";
			}
		}
		//cout<<"*2*\n";
		for(auto v:v0)
		{
			if(status[v.pos]=="MA")
			{
				MiddleActive.erase(t[v.pos]);
				LeftActive.insert(t[v.pos]);
				status[v.pos]="LA";
			}
			if(status[v.pos]=="MU")
			{
				MiddleUnactive.erase(t[v.pos]);
				LeftUnactive.insert(t[v.pos]);
				status[v.pos]="LU";
			}
		}
		//cout<<"*3*\n";
		while(LeftActive.size()+RightActive.size()+MiddleActive.size()<k)
		{
			//cout<<LeftActive.size()+RightActive.size()+MiddleActive.size()<<endl;
			//cout<<"*"<<LeftUnactive.size()<<" "<<MiddleUnactive.size()<<" "<<RightUnactive.size()<<endl;
			//cout<<total_win<<endl;
			if(LeftUnactive.size()+MiddleUnactive.size()+RightUnactive.size()==0)break;
			pair<pair<ll,tower>,string>leu;
			leu={{INF,{0ll,0ll,0ll}},"no"};
			ll cost;
			if(LeftUnactive.size()!=0)
			{
				auto f=(*LeftUnactive.begin());
				cost=f.s+line.first-f.r;
				leu=min(leu,{{cost,f},"LU"});
			}
			if(MiddleUnactive.size()!=0)
			{
				auto f=(*MiddleUnactive.begin());
				cost=f.s;
				leu=min(leu,{{cost,f},"MU"});
			}
			if(RightUnactive.size()!=0)
			{
				auto f=(*RightUnactive.begin());
				cost=f.s+f.l-line.first;
				leu=min(leu,{{cost,f},"RU"});
			}
			//cout<<"^"<<leu.first.first<<endl;
			total_win-=leu.first.first;
			if(status[leu.first.second.pos]=="LU")
			{
				LeftUnactive.erase(leu.first.second);
				LeftActive.insert(leu.first.second);
				status[leu.first.second.pos]="LA";
			}
			else if(status[leu.first.second.pos]=="MU")
			{
				MiddleUnactive.erase(leu.first.second);
				MiddleActive.insert(leu.first.second);
				status[leu.first.second.pos]="MA";
			}
			else if(status[leu.first.second.pos]=="RU")
			{
				RightUnactive.erase(leu.first.second);
				RightActive.insert(leu.first.second);
				status[leu.first.second.pos]="RA";
			}
		}
		//cout<<"*4*\n";
		for(;;)
		{
			//cout<<LeftActive.size()+MiddleActive.size()+RightActive.size()<<" "<<k<<endl;
			//cout<<LeftActive.size()<<" "<<LeftUnactive.size()<<" "<<MiddleActive.size()<<" "<<MiddleUnactive.size()<<" "<<RightActive.size()<<" "<<RightUnactive.size()<<endl;
			pair<pair<ll,tower>,string>mea,leu;
			mea={{(ll)-1,{0ll,0ll,0ll}},"no"};
			leu={{INF,{0ll,0ll,0ll}},"no"};
			ll cost;
			if(LeftUnactive.size()!=0)
			{
				auto f=(*LeftUnactive.begin());
				cost=f.s+line.first-f.r;
				leu=min(leu,{{cost,f},"LU"});
			}
			if(MiddleUnactive.size()!=0)
			{
				auto f=(*MiddleUnactive.begin());
				cost=f.s;
				leu=min(leu,{{cost,f},"MU"});
			}
			if(RightUnactive.size()!=0)
			{
				auto f=(*RightUnactive.begin());
				cost=f.s+f.l-line.first;
				leu=min(leu,{{cost,f},"RU"});
			}
			if(LeftActive.size()!=0)
			{
				auto it=LeftActive.end();
				it--;
				auto f=(*it);
				cost=f.s+line.first-f.r;
				mea=max(mea,{{cost,f},"LA"});
			}
			if(MiddleActive.size()!=0)
			{
				auto it=MiddleActive.end();
				it--;
				auto f=(*it);
				cost=f.s;
				mea=max(mea,{{cost,f},"MA"});
			}
			if(RightActive.size()!=0)
			{
				auto it=RightActive.end();
				it--;
				auto f=(*it);
				cost=f.s+f.l-line.first;
				mea=max(mea,{{cost,f},"RA"});
			}
			//cout<<mea.first.first<<" "<<leu.first.first<<endl;
			if(mea.first.first<=leu.first.first)
			{
				break;
			}
			total_win+=mea.first.first;
			total_win-=leu.first.first;
			if(status[leu.first.second.pos]=="LU")
			{
				LeftUnactive.erase(leu.first.second);
				LeftActive.insert(leu.first.second);
				status[leu.first.second.pos]="LA";
			}
			else if(status[leu.first.second.pos]=="MU")
			{
				MiddleUnactive.erase(leu.first.second);
				MiddleActive.insert(leu.first.second);
				status[leu.first.second.pos]="MA";
			}
			else if(status[leu.first.second.pos]=="RU")
			{
				RightUnactive.erase(leu.first.second);
				RightActive.insert(leu.first.second);
				status[leu.first.second.pos]="RA";
			}
			if(status[mea.first.second.pos]=="LA")
			{
				LeftActive.erase(mea.first.second);
				LeftUnactive.insert(mea.first.second);
				status[mea.first.second.pos]="LU";
			}
			else if(status[mea.first.second.pos]=="MA")
			{
				MiddleActive.erase(mea.first.second);
				MiddleUnactive.insert(mea.first.second);
				status[mea.first.second.pos]="MU";
			}
			else if(status[mea.first.second.pos]=="RA")
			{
				RightActive.erase(mea.first.second);
				RightUnactive.insert(mea.first.second);
				status[mea.first.second.pos]="RU";
			}
		}
		//cout<<"*5*\n";
		ans=max(ans,total_win);
		//cout<<total_win<<endl;
		last=line.first;
	}
	cout<<-ans<<endl;
return 0;
}

Compilation message (stderr)

radio.cpp: In function 'int main()':
radio.cpp:111:65: warning: comparison of integer expressions of different signedness: 'std::set<tower, bool (*)(tower, tower)>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  111 |   while(LeftActive.size()+RightActive.size()+MiddleActive.size()<k)
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 25 / 25