oj.uz

Submission #1115995

# Submission time Handle Problem Language Result Execution time Memory
1115995 2024-11-21T07:26:55 Z NotLinux Autobahn (COI21_autobahn) C++17
0 / 100
 1 ms 504 KB 
// Author : FatihCihan
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
void solve(){
	int n,k,x;
	cin >> n >> k >> x;
	int l[n] , t[n] , r[n];
	vector < int > comp = {0};
	for(int i = 0;i<n;i++){
		cin >> l[i] >> t[i] >> r[i];
		t[i] = min(t[i] , r[i] - l[i] + 1);

		comp.push_back(l[i] - 1);
		comp.push_back(l[i]);
		comp.push_back(l[i] + 1);

		comp.push_back(l[i] + t[i] - 1);
		comp.push_back(l[i] + t[i]);
		comp.push_back(l[i] + t[i] + 1);

		comp.push_back(r[i] - 1);
		comp.push_back(r[i]);
		comp.push_back(r[i] + 1);
	}
	sort(all(comp));
	comp.resize(unique(all(comp)) - comp.begin());
	auto fnd = [&](int x){
		return lower_bound(all(comp),x) - comp.begin();
	};
	int m = sz(comp);
	comp.push_back(comp.back());
	int st[m+5]={0} , fault[m+5]={0} , en[m+5]={0};
	for(int i = 0;i<n;i++){
		st[fnd(l[i])]++;
		fault[fnd(l[i] + t[i] - 1) + 1]++;
		en[fnd(r[i]) + 1]++;
	}
	int cur_valid=0 , cur_fault=0 , charge[m]={0};
	for(int i = 0;i<m;i++){
		cur_valid += st[i];
		cur_valid -= fault[i];
		cur_fault += fault[i];
		cur_fault -= en[i];
		if(cur_valid + cur_fault >= k){
			charge[i] = cur_fault;
		}
	}	
	// for(int i = 0;i<m;i++){
	// 	cout << comp[i] << " : " << charge[i] << endl;
	// }
	int ans = 0 , cur_ans = 0 , rp = 0;
	for(int i = 0;i<m;i++){
		// cout << "st : " << i << " " << rp << " : " << cur_ans << endl;
		while(rp < m and comp[rp] - comp[i] < x){
			cur_ans += charge[rp] * (comp[rp+1] - comp[rp]);
			rp++;
			// cout << i << " " << rp << " : " << cur_ans << endl;
		}
		int reel_ans = cur_ans - charge[rp-1] * (comp[rp] - comp[i] - x);
		ans = max(ans , reel_ans);
		// cout << "en : " << i << " " << rp << " : " << reel_ans << endl;
		cur_ans -= charge[i] * (comp[i+1] - comp[i]);
	}
	cout << ans << endl;
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
	cerr << 1000.0 * clock() / CLOCKS_PER_SEC << " ms" << endl;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 504 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Incorrect 1 ms 336 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 504 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Incorrect 1 ms 336 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 504 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Incorrect 1 ms 336 KB Output isn't correct
12 Halted 0 ms 0 KB -