Submission #582698

#	Time	Username	Problem	Language	Result	Execution time	Memory
582698		chirathnirodha	Autobahn (COI21_autobahn)	C++17	100 / 100	133 ms	16888 KiB

autobahn

//Coded by Chirath Nirodha
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
using namespace std;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define P push
#define I insert
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
const ll mod=1e9+7;
inline void io(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}
void solve(){
    io();
	ll n,k,x;cin>>n>>k>>x;
  	ll l,t,r;
	vector<pair<ll,int> > v;
	for(int i=0;i<n;i++){
		cin>>l>>t>>r;
		l--;
		v.PB(MP(l,1));
		v.PB(MP(r,2));
		v.PB(MP(l+x,3));
		v.PB(MP(r+x,4));
		if(r-l-t<=0)continue;
		v.PB(MP(l+t,5));
		v.PB(MP(r,6));
		v.PB(MP(l+t+x,7));
		v.PB(MP(r+x,8));
	}
	sort(v.begin(),v.end());
	ll pos=-x,inc=0,dec=0,cnt=0,cntp=0,val=0;
	ll ans=0;
	for(int i=0;i<v.size();i++){
		ll d=v[i].F-(pos+x);
		if(cnt>=k)val+=inc*d;
		if(cntp>=k)val+=dec*d;
		ans=max(ans,val);
		if(v[i].S==1)cnt++;
		else if(v[i].S==2)cnt--;
		else if(v[i].S==3)cntp++;
		else if(v[i].S==4)cntp--;
		else if(v[i].S==5)inc++;
		else if(v[i].S==6)inc--;
		else if(v[i].S==7)dec--;
		else dec++;
		pos+=d;
	}
	cout<<ans<<endl;
}
int main(){
    io();
	solve();
	//int t;cin>>t;for(int i=0;i<t;i++)solve();
    return 0;
}

Compilation message (stderr)

autobahn.cpp: In function 'void solve()':
autobahn.cpp:43:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  for(int i=0;i<v.size();i++){
      |              ~^~~~~~~~~

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