Submission #1002874

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002874		PagodePaiva	Autobahn (COI21_autobahn)	C++17	100 / 100	370 ms	35996 KiB

autobahn

#include<bits/stdc++.h>
#define endl '\n'
#define int long long

using namespace std;

const int debug = 0;
const int N = 1e5+20;
map <int, vector <int>> tempos;

int32_t main(){
	int n, k, x;
	cin >> n >> k >> x;
	for(int i = 0;i < n;i++){
		int l, t, r;
		cin >> l >> t >> r;
		tempos[l].push_back(0);
		tempos[r+1].push_back(1);
		tempos[l+t].push_back(2);
		tempos[r+1].push_back(3);
	}
	int r = 0, l = -x+1;
	int qtdl = 0, qtdr = 0, vall = 0, valr = 0;
	int res = 0, soma = 0;
	while(tempos.upper_bound(r) != tempos.end()){
		//cout << l << ' ' << r << endl;
		auto it = tempos.upper_bound(l);
		int l1 = it->first;
		it = tempos.upper_bound(r);
		int r1 = it->first;
		//cout << l1 << ' ' << r1 << endl;
		if(l1-l < r1-r){
			// vou do [l, r] ate [l1-1, l1-1+x-1]
			// l1-l
			soma -= (qtdl >= k)*vall*(l1-l-1);
			// l1-1+x-r
			soma += (qtdr >= k)*valr*(l1+x-r-2);
			res = max(res, soma);
			l = l1-1;
			r = l1-1+x-1;
			soma -= (qtdl >= k)*vall;
			l++;
			r++;
			for(auto typ : tempos[l]){
				if(typ == 0) qtdl++;
				if(typ == 1) qtdl--;
				if(typ == 2) vall++;
				if(typ == 3) vall--;
			}
			soma += (qtdr >= k)*valr;
			res = max(res, soma);
		}
		else if(l1-l > r1-r){
			// vou do [l, r] ate [r1-x, r1-1]
			//r1-x-l+1
			soma -= (qtdl >= k)*vall*(r1-x-l);
			soma += (qtdr >= k)*valr*(r1-r-1);
			res = max(res, soma);
			l = r1-x;
			r = r1-1;
			soma -= (qtdl >= k)*vall;
			l++;
			r++;
			for(auto typ : tempos[r]){
				if(typ == 0) qtdr++;
				if(typ == 1) qtdr--;
				if(typ == 2) valr++;
				if(typ == 3) valr--;
			}
			soma += (qtdr >= k)*valr;
			res = max(res, soma);
		}
		else{
			soma -= (qtdl >= k)*vall*(r1-x-l);
			soma += (qtdr >= k)*valr*(r1-r-1);
			res = max(res, soma);
			l = l1-1;
			r = l1-1+x-1;
			soma -= (qtdl >= k)*vall;
			l++;
			r++;
			for(auto typ : tempos[l]){
				if(typ == 0) qtdl++;
				if(typ == 1) qtdl--;
				if(typ == 2) vall++;
				if(typ == 3) vall--;
			}
			for(auto typ : tempos[r]){
				if(typ == 0) qtdr++;
				if(typ == 1) qtdr--;
				if(typ == 2) valr++;
				if(typ == 3) valr--;
			}
			soma += (qtdr >= k)*valr;
			res = max(res, soma);
		}
	}
	cout << res << endl;
	return 0;
}

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