제출 #582696

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
582696		chirathnirodha	Autobahn (COI21_autobahn)	C++17	100 / 100	148 ms	21264 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[n],r[n],t[n];
	vector<pair<ll,int> > v;
	for(int i=0;i<n;i++){
		cin>>l[i]>>t[i]>>r[i];
		l[i]--;
		v.PB(MP(l[i],1));
		v.PB(MP(r[i],2));
		v.PB(MP(l[i]+x,3));
		v.PB(MP(r[i]+x,4));
		if(r[i]-l[i]-t[i]<=0)continue;
		v.PB(MP(l[i]+t[i],5));
		v.PB(MP(r[i],6));
		v.PB(MP(l[i]+t[i]+x,7));
		v.PB(MP(r[i]+x,8));
	}
	sort(v.begin(),v.end());
	ll pos=-x,inc=0,dec=0,cnt=0,val=0,cntp=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;
}

컴파일 시 표준 에러 (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