oj.uz

Submission #962180

# Submission time Handle Problem Language Result Execution time Memory
962180 2024-04-13T08:37:47 Z LCJLY Autobahn (COI21_autobahn) C++14
50 / 100
 730 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;	
 
#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<long long,int>pii;
typedef pair<int,pii>pi2;

inline int combine(int a, int b){
	return a+b;
}

struct node{
	int s,e,m;
	node *l,*r;
	int v;
	int lazyUpd;
	
	node(int ss, int ee):s(ss),e(ee),m((s+e)>>1),l(NULL),r(NULL),v(0),lazyUpd(0){
	}
	
	inline void inst(){
		if(l==NULL) l=new node(s,m);
		if(r==NULL) r=new node(m+1,e);
	}
	
	void self_add(int x){
		v+=(e-s+1)*x;
		lazyUpd+=x;
	}
	
	void forceProp(){
		if(s==e) return;
		if(lazyUpd){
			l->self_add(lazyUpd),r->self_add(lazyUpd);
			lazyUpd=0;
		}
	}
	
	void rangeUpd(int x, int y, int c){
		if(x<=s&&y>=e){
			self_add(c);
			return;
		}
		inst();
		forceProp();
		if(x<=m) l->rangeUpd(x,y,c);
		if(y>m){
			r->rangeUpd(x,y,c);
		}
		v=combine(l->v,r->v);
	}	
	
	int query(int x, int y){
		if(x<=s&&y>=e){
			return v;
		}
		inst();
		forceProp();
		if(y<=m) return l->query(x,y);
		if(x>m) return r->query(x,y);
		return combine(l->query(x,m),r->query(m+1,y)); 
	}
};

struct event{
	int type, sign;
	event(int tt, int ss):type(tt),sign(ss){}
};

void solve(){
	int n,k,m;
	cin >> n >> k >> m;
	
	int temp,temp2,temp3;
	map<int,vector<event>>mp;
	for(int x=0;x<n;x++){
		cin >> temp >> temp2 >> temp3;
		event hold(0,1);
		event hold2(0,-1);
		mp[temp].push_back(hold);
		mp[temp+temp2].push_back(hold2);
		
		if(temp+temp2<=temp3){
			event hold3(1,1);
			event hold4(1,-1);
			mp[temp+temp2].push_back(hold3);
			mp[temp3+1].push_back(hold4);
		}
	}
	
	int last=0;
	int car=0;
	int unpaid=0;
	node st(0,1e9+5);
	vector<int>v;
	
	for(auto index:mp){
		//show(index.first,index.first);
		if(car>=k){
			//show2(last,last,index.first-1,index.first-1);
			st.rangeUpd(last,index.first-1,unpaid);
			//show(upd,1);
			v.push_back(index.first-1);
			v.push_back(last+m-1);
		}
		
		for(auto it:index.second){
			if(it.type==0){
				//paid
				car+=it.sign;
			}
			else{
				//unpaid
				car+=it.sign;
				unpaid+=it.sign;
			}
		}
		last=index.first;
	}
	
	int best=0;
	for(auto it:v){
		int r=min(it,(int)1e9+5);
		int l=max(r-m+1,0LL);
		best=max(best,st.query(l,r));
	}
	cout << best;
}
 
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 1 ms 592 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 2 ms 604 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 1 ms 592 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 2 ms 604 KB Output is correct
21 Runtime error 730 ms 524288 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -