Submission #1218609

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218609		_rain_	Autobahn (COI21_autobahn)	C++20	100 / 100	365 ms	51672 KiB

autobahn

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=(int)1e5;
	int n,k,x;
	int l[N+2],t[N+2],r[N+2];
	vector<int>nen,pon;
	LL pre[N+2]={};
	int Find(int x){
		return upper_bound(nen.begin(),nen.end(),x)-nen.begin();
	}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0);
	#define task "main"
	if (fopen(task".inp","r")){
		freopen(task".inp","r",stdin);
		freopen(task".out","w",stdout);
	}
	
	cin>>n>>k>>x;
	for(int i=1;i<=n;++i){
		cin>>l[i]>>t[i]>>r[i];
		nen.push_back(l[i]);
		nen.push_back(r[i]);
		nen.push_back(r[i]+1);
		nen.push_back(l[i]+t[i]);
	}
	sort(nen.begin(),nen.end());
	nen.resize(unique(nen.begin(),nen.end())-nen.begin());
	vector<int>pon=nen;
	for(int i=0;i<pon.size();++i){
		nen.push_back(pon[i]+x-1);
		nen.push_back(pon[i]-x+1);
		nen.push_back(pon[i]-x);
		nen.push_back(pon[i]+x);
		nen.push_back(pon[i]-1);
		nen.push_back(pon[i]+1);
	}
	sort(nen.begin(),nen.end());
	nen.resize(unique(nen.begin(),nen.end())-nen.begin());
	vector<int>dem(nen.size()+2,0),f(nen.size()+2,0);
	vector<LL>pre(nen.size()+2,0);
	for(int i=1;i<=n;++i){
		dem[Find(l[i])]++,dem[Find(r[i]+1)]--;
		f[Find(l[i]+t[i])]++,f[Find(r[i]+1)]--;
	}
	for(int i=1;i<=nen.size();++i) {
		dem[i]+=dem[i-1];
		f[i]+=f[i-1];
	}
	for(int i=1;i<=nen.size();++i) dem[i]=(dem[i]>=k?1:0);
	for(int i=1;i<=nen.size();++i){
		pre[i]=pre[i-1];
		if (i<nen.size()) pre[i]+=(LL)dem[i]*f[i]*(nen[i]-nen[i-1]);
	}
	LL ans=0;
	for(auto&u:pon){
		int l=u,r=u-x+1;
		ans=max(ans,pre[Find(l)]-pre[Find(r)-1]);
		l=u,r=u+x-1;
		ans=max(ans,pre[Find(r)]-pre[Find(l)-1]);
	}
	cout<<ans;
}

Compilation message (stderr)

autobahn.cpp: In function 'int main()':
autobahn.cpp:18:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |                 freopen(task".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
autobahn.cpp:19:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |                 freopen(task".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50