Submission #962180

#	Time	Username	Problem	Language	Result	Execution time	Memory
962180		LCJLY	Autobahn (COI21_autobahn)	C++14	50 / 100	730 ms	524288 KiB

autobahn

#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 / 20
• Subtask 2: 30 / 30
• Subtask 3: 0 / 50