Submission #962211

#	Time	Username	Problem	Language	Result	Execution time	Memory
962211		LCJLY	Autobahn (COI21_autobahn)	C++14	0 / 100	0 ms	352 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 long long combine(long long a, long long b){
	return a+b;
}

struct node{
	int s,e,m;
	node *l,*r;
	long long v;
	long long 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);
	}	
	
	long long 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<int>>mp;
	for(int x=0;x<n;x++){
		cin >> temp >> temp2 >> temp3;
		//event hold(0,1);
		//event hold2(0,-1);
		mp[temp].push_back(1);
		mp[temp+temp2].push_back(2);
		
		if(temp+temp2<=temp3){
			//event hold3(1,1);
			//event hold4(1,-1);
			mp[temp+temp2].push_back(3);
			mp[temp3+1].push_back(4);
		}
	}
	
	int last=0;
	int car=0;
	int unpaid=0;
	//node st(0,1e9+5);
	vector<int>v;
	deque<pair<pii,int>>d;
	
	for(auto index:mp){
		//show(index.first,index.first);
		if(car>=k){
			//st.rangeUpd(last,index.first-1,unpaid);
			d.push_back({{last,index.first-1},unpaid});
			//d2.push_back({{last,index.first-1},unpaid});
			v.push_back(index.first-1);
			v.push_back(last+m-1);
		}
		
		for(auto it:index.second){
			if(it==1||it==2){
				//paid
				if(it==1) car++;
				else car--;
			}
			else{
				//unpaid
				if(it==3){
					car++;
					unpaid++;
				}
				else{
					car--;
					unpaid--;
				}
			}
		}
		last=index.first;
	}
	
	long long best=0;
	long long counter=0;
	int ptr=0;
	
	//for(auto it:d){
		//cout << it.first.first <<  " " << it.first.second << " " << it.second << endl;
	//}
	
	for(int x=0;x<(int)d.size();x++){
		counter+=(d[x].first.second-d[x].first.first+1)*d[x].second;
		int l=d[x].first.second-m+1;
		while(ptr<(int)d.size()&&l>d[ptr].first.second){
			counter-=(d[ptr].first.second-d[ptr].first.first+1)*d[ptr].second;
			ptr++;
		}
		int add=0;
		if(l>=d[ptr].first.first){
			add=-(l-d[ptr].first.first);
		}
		best=max(best,counter+add);
		//show(counter,counter);
	}
	
	//show(best,best);
	
	ptr=(int)d.size()-1;
	counter=0;
	for(int x=(int)d.size()-1;x>=0;x--){
		counter+=(d[x].first.second-d[x].first.first+1)*d[x].second;
		int r=d[x].first.first+m-1;
		while(ptr>=0&&r<d[ptr].first.first){
			counter-=(d[ptr].first.second-d[ptr].first.first+1)*d[ptr].second;
			ptr--;
		}
		int add=0;
		if(r<=d[ptr].first.second){
			add=-(d[ptr].first.second-r);
		}
		best=max(best,counter+add);
	}
	
	cout << best;
}
 
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}
}

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