Submission #1002648

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002648		Lalic	Autobahn (COI21_autobahn)	C++17	50 / 100	68 ms	16048 KiB

autobahn

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define mp make_pair

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<double> cd;

const int MAXN = 1e5+10;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);

struct occ{
	ll x;
	int tipo, val;
	
	occ(ll a, int b, int c): x(a), tipo(b), val(c) {}
	
	bool operator < (occ a) const{
		return this->x < a.x;
	}
};

void solve(){
	int n, k, x; cin >> n >> k >> x;
	vector<occ> arr;
	
	for(int i=0;i<n;i++){
		ll l, t, r; cin >> l >> t >> r;
		
		arr.pb(occ(l, 0, 1));
		arr.pb(occ(r+1, 0, -1));
		if(l+t<=r){
			arr.pb(occ(l+t, 1, 1));
			arr.pb(occ(r+1, 1, -1));
		}
	}
	
	sort(all(arr));
	arr.pb(occ(INF, 0, 0));
	
	int low=-x, high=0, ptrl=0, ptrh=0;
	ll normH=0, normL=0, specH=0, specL=0, curr=0, ans=0;
	while(1){
		if(ptrh==(int)arr.size()-1 && ptrl==(int)arr.size()-1) break;
		
		if(arr[ptrh].x-high<=arr[ptrl].x-low){
			ll diff=arr[ptrh].x-high;
			if(normH>=k) curr+=specH*diff;
			if(normL>=k) curr-=specL*diff;
			
			if(arr[ptrh].tipo==0) normH+=arr[ptrh].val;
			else specH+=arr[ptrh].val;
			
			high+=diff;
			low+=diff;
			ptrh++;
		}
		else{
			ll diff=arr[ptrl].x-low;
			if(normH>=k) curr+=specH*diff;
			if(normL>=k) curr-=specL*diff;
			
			if(arr[ptrl].tipo==0) normL+=arr[ptrl].val;
			else specL+=arr[ptrl].val;
			
			high+=diff;
			low+=diff;
			ptrl++;
		}
		
		while(arr[ptrh].x-high==0){
			if(arr[ptrh].tipo==0) normH+=arr[ptrh].val;
			else specH+=arr[ptrh].val;
			ptrh++;
		}
		
		while(arr[ptrl].x-low==0){
			if(arr[ptrl].tipo==0) normL+=arr[ptrl].val;
			else specL+=arr[ptrl].val;
			ptrl++;
		}
		
		ans=max(ans, curr);
	}
	
	cout << ans << "\n";
}
	

int32_t main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	
	int tt=1;
	//~ cin >> tt;
	while(tt--) solve();
	return 0;
}

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