Submission #1003666

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003666		Sofiatpc	Autobahn (COI21_autobahn)	C++14	0 / 100	1 ms	2396 KiB

autobahn

#include <bits/stdc++.h>

using namespace std;

#define sz(v) (int)v.size()
struct event{
	int t,x, id;
	bool operator < (event b){
		if(x == b.x)return t < b.t;
		return x < b.x;
	}
};
const int MAXN = 1e5+5;
int l[MAXN], t[MAXN], r[MAXN], ans[MAXN*3];
vector<event> e;
set<int> q;

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int n,k,x; cin>>n>>k>>x;
	
	for(int i = 1; i <= n; i++){
		cin>>l[i]>>t[i]>>r[i];
		t[i] += l[i]; r[i]++;

		event fim; fim.t = 1; fim.x = r[i]; fim.id = 0;
		if(t[i] >= r[i])fim.id = 1;
		e.push_back(fim);

		event ini; ini.t = 2; ini.x = l[i]; e.push_back(ini);

		if(t[i] < r[i]){event iniP; iniP.t = 3; iniP.x = t[i]; e.push_back(iniP);}

		q.insert(r[i]); q.insert(l[i]); q.insert(t[i]);
	}

	int curi = 0;
	for(int i : q){
		event temp; temp.x = i-1; temp.t = 4; 
		temp.id = curi; curi++;
		e.push_back(temp);

		temp.t = 5; temp.x = i+x+1;
		e.push_back(temp);
	}

	sort(e.begin(),e.end());

	int curk = 0, pag = 0, lq = 0, pq = 0;
	for(int i = 0; i < sz(e); i++){
		if(e[i].t == 1){
			curk--; 
			if(e[i].id == 0)pag--;
		}else if(e[i].t == 2)curk++;
		else if(e[i].t == 3)pag++;
		else if(e[i].t == 4){
			int x = pq;
			if(curk >= k)x += (e[i].x-lq)*pag;
			pq = x; lq = e[i].x;
			ans[e[i].id] += x;
		}
	}

	int total = pq;
	curk = 0, pag = 0, lq = 0, pq = 0;
	for(int i = 0; i < sz(e); i++){
		if(e[i].t == 1){
			curk--; 
			if(e[i].id == 0)pag--;
		}else if(e[i].t == 2)curk++;
		else if(e[i].t == 3)pag++;
		else if(e[i].t == 5){
			int x = pq;
			if(curk >= k)x += (e[i].x-lq)*pag;
			ans[e[i].id] += (total-x);
			pq = x; lq = e[i].x;
		}
	}

	int resp = 0;
	for(int i = 0; i < curi; i++)resp = max(resp, total-ans[i]);
	cout<<resp<<"\n";
}

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