제출 #965026

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
965026		peacebringer1667	Autobahn (COI21_autobahn)	C++17	0 / 100	41 ms	73052 KiB

autobahn

#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define fi first
#define se second
using namespace std;
const int maxn = 3e5 + 5;
struct CTDL{
	int l = 0,r = 0,t = 0;
	bool operator <(const CTDL&other) const{
		if (l < other.l) return 1;
		if (l > other.l) return 0;
		return (r < other.r);
	}
};
bool cmp(pair <int,int> x,pair <int,int> y){
	if (x.se < y.se) return 1;
	if (x.se > y.se) return 0;
	return (x.fi < y.fi);
}
struct DSA{
    vector <pair<int,int>> L,R;
    vector <ll> SLfi,SLse,SRfi,SRse,preL,preR;
    
    ll sum = 0,sumR = 0;
    
    void prep(){
    	 int N = L.size();
    	 
         for (int i = 0 ; i < N ; i++){
         	if (i){
         	   preL[i] = preL[i - 1];
			   SLfi[i] = SLfi[i - 1];
			   SLse[i] = SLse[i - 1];	
			 }
			
			preL[i] += L[i].se - L[i].fi + 1;
			SLfi[i] += L[i].fi;
			SLse[i] += L[i].se;
		 }	
		 
		 
		 for (int i = 0 ; i < N ; i++){
		 	if (i){
		 		preR[i] = preR[i - 1];
		 		SRfi[i] = SRfi[i - 1];
		 		SRse[i] = SRse[i - 1];
			 }
			 
			 preR[i] += R[i].se - R[i].fi + 1;
			 SRfi[i] += R[i].fi;
			 SRse[i] += R[i].se;
		 }
	}
	void inputarr(const vector <pair<int,int>> &vec){
		for (pair <int,int> x : vec){
			L.push_back(x);
			R.push_back(x);
			preL.push_back(0);
			preR.push_back(0);
			SLfi.push_back(0);
			SLse.push_back(0);
			SRfi.push_back(0);
			SRse.push_back(0);
			sum += x.se - x.fi + 1;
		}
		
		sort(L.begin(),L.end());
		sort(R.begin(),R.end(),cmp);
		prep();
	}
    
    ll dif(int vt,bool type){
    	ll res = 0;
    	int N = L.size();
    	
    	if (!type){
    		pair <int,ll> C;
    		
    		int l = 0,r = R.size() - 1,vt1 = -1;
    		while (l <= r){
    			int w = (l + r)/2;
    			if (R[w].se < vt){
    				vt1 = w;
    				l = w + 1;
				}
				else r = w - 1;
			}
			
			l = 0;r = L.size() - 1;int vt2 = N;
		    while (l <= r){
		    	int w = (l + r)/2;
		    	if (L[w].fi > vt){
		    		vt2 = w;
		    		r = w - 1;
				}
				else l = w + 1;
			}
	     		
		C.se = SLfi[N - 1];
		C.fi = N;
		
		if (vt1 != -1){
			C.fi -= vt1 + 1;
			C.se -= SRfi[vt1];
		}
		
		if (vt2 != N){
			C.fi -= (N - vt2);
			
			ll T = 0;
			if (vt2 != 0)
			  T = SLfi[vt2 - 1];
			C.se -= (SLfi[N - 1] - T);
		}
		
		res = (ll)C.fi*(ll)vt - C.se;
		}
		else{
			pair <int,ll> C;
			C.fi = N;
			C.se = SLse[N - 1];
			
			int l = 0,r = N - 1,vt1 = -1;
			while (l <= r){
				int w = (l + r)/2;
				if (R[w].se < vt){
					vt1 = w;
					l = w + 1;
				}
				else r = w - 1;
			}
			
			l = 0;r = N - 1;int vt2 = -1;
			while (l <= r){
				int w = (l + r)/2;
				if (L[w].fi > vt){
					vt2 = w;
					r = w - 1;
				}
				else l = w + 1;
			}
			
			if (vt1 != -1){
				C.fi -= vt1 + 1;
				C.se -= SRse[vt1];
			}
			if (vt2 != -1){
				C.fi -= (N - vt2);
				
				ll T = 0;
				if (vt2 != 0)
				  T = SLse[vt2 - 1];
				  
				C.se -= SLse[N - 1] - T; 
			}
			
			res = C.se - (ll)C.fi*(ll)vt;
		}
		return res;
	}
    
    ll outs(int vt,bool type){
    	ll res = 0;
    	int N = L.size();
    	if (!type){
    		int l = 0,r = N - 1,vt1 = -1;
		    
			while (l <= r){
		    	int w = (l + r)/2;
		        if (R[w].se < vt){
		        	vt1 = w;
		        	l = w + 1;
				}	
				else r = w - 1;
			}
			
	        if (vt1 != -1)
			  res = preR[vt1];
		}
		else{
			int l = 0,r = N - 1,vt1 = -1;
			
			while (l <= r){
				int w = (l + r)/2;
				if (L[w].fi > vt){
					vt1 = w;
					r = w - 1;
				}
				else l = w + 1;
			}
			
			if (vt1 != -1){
				res = preL[N - 1];
				
				if (vt1 != 0)
				  res -= preL[vt1 - 1];
			}
		}
		return res;
	}
    
    ll getval(int l,int r){
    	ll T = sum;
    	T -= dif(l,0);
    	T -= dif(r,1);
    	
    	T -= outs(l,0);
    	T -= outs(r,1);
    	return T;
	}
    
    ll calc(int l,int r){
    	if (!L.size() || l > R.back().se || r < L[0].fi) return 0;
    	if (l <= L[0].fi && r >= R.back().se) return sum;
    	l = max(l,L[0].fi);
    	r = min(r,R.back().se);
    	
    	return getval(l,r);
	}
};

int C[maxn];
ll pre[maxn];
priority_queue <int,vector<int>,greater<int>> pq;
vector <pair<int,int>> ak;
vector <vector<pair<int,int>>> vec(maxn);
DSA lst[maxn];
CTDL a[maxn];

void prepare(int n,int k){
	sort(a + 1,a + 1 + n);
	for (int i = 1 ; i <= n ; i++){
	    pq.push(a[i].r);
		while (pq.size() > k) pq.pop();
		
		if (pq.size() >= k){
		   int T = pq.top();
		   if (T >= a[i].l)
		      ak.push_back({a[i].l,T});
	    }
	}
	sort(ak.begin(),ak.end());
}

void simplify(){
	vector <pair<int,int>> tmp;
	int p = 0;
	while (p < ak.size()){
		int P = p;
		int lim = ak[p].se;
		
		while (P < ak.size() && ak[P].fi <= lim){
		  lim = max(lim,ak[P].se);
		  P++;
	    }
		P--;
		tmp.push_back({ak[p].fi,ak[P].se});
		p = P + 1;
	}
	ak = tmp;
	sort(ak.begin(),ak.end());
}

void perf(int p,int l,int r){
	if (r < ak[p].fi || l > ak[p].se) return;
	if (l == ak[p].fi && r == ak[p].se){
		C[p]++;
		C[p + 1]--;
	    return;
	}
    
    l = max(l,ak[p].fi);
    r = min(r,ak[p].se);
    
    vec[p].push_back({l,r});
}

void add_to_arr(int L,int R){
	if (R < ak[0].fi || L > ak.back().se) return;
	
	int l = 0,r = ak.size() - 1,d = 0,c = ak.size();
	
	while (l <= r){
		int w = (l + r)/2;
		if (ak[w].se >= L){
			d = w;
			r = w - 1;
		}
		else l = w + 1;
	}
	
	l = 0;r = ak.size() - 1;
	while (l <= r){
		int w = (l + r)/2;
		if (ak[w].fi <= R){
			c = w;
			l = w + 1;
		}
		else r = w - 1;
	}
	
	if (d > c) return;
	perf(d,L,R);
	
	if (d != c){
		perf(c,L,R);
		C[d + 1]++;
		C[c]--;	  
	}
}

void genarr(int n,int k){
	for (int i = 1 ; i <= n ; i++)
	  if (a[i].l + a[i].t <= a[i].r)
	    add_to_arr(a[i].l + a[i].t,a[i].r);
}

void deeppre(int p){
	if (!vec[p].size()) return;
	lst[p].inputarr(vec[p]);
}

void getpre(){
	int N = ak.size() - 1;
	pre[0] = (ll)C[0]*(ll)(ak[0].se - ak[0].fi + 1);
	deeppre(0);
	
	for (int i = 1 ; i <= N ; i++){
		C[i] += C[i - 1];
		pre[i] = pre[i - 1] + (ll)C[i]*(ll)(ak[i].se - ak[i].fi + 1);
		deeppre(i);
	}
}

ll solve(int l,int r){
	ll res = 0;
	if (l > ak.back().se || r < ak[0].fi) return 0;
	
	int d = 0,c = ak.size() - 1,vt1 = -1;
	while (d <= c){
		int w = (d + c)/2;
		if (ak[w].se >= l){
			vt1 = w;
			c = w - 1;
		}
		else d = w + 1;
	}
	
	int vt2 = -1;
	d = 0;c = ak.size() - 1;
	while (d <= c){
		int w = (d + c)/2;
		if (ak[w].fi <= r){
			vt2 = w;
			d = w + 1;
		}
		else c = w - 1;
	}
	if (vt1 > vt2) return 0;
	
	if (vt1 == vt2) return lst[vt1].calc(l,r);
	
	res = lst[vt1].calc(l,r) + lst[vt2].calc(l,r);
	res += pre[vt2 - 1] - pre[vt1];
	
	return res;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
    int n,k,x;
    cin >> n >> k >> x;
    for (int i = 1 ; i <= n ; i++)
    	cin >> a[i].l >> a[i].t >> a[i].r;
	
	prepare(n,k);
	if (!ak.size()){
		cout << 0;
		return 0;
	}
	
	simplify();
	genarr(n,k);
	getpre();
	
	ll res = 0;
	for (int i = 1 ; i <= n ; i++){
	   res = max(res,solve(a[i].l,a[i].l + x - 1));
	   res = max(res,solve(a[i].l + a[i].t,a[i].l + a[i].t + x - 1));
	   if (a[i].r >= x)
	     res = max(res,solve(a[i].r - x + 1,a[i].r));
    }
    
    cout << res;
//	cout << solve(x);
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

autobahn.cpp: In function 'void prepare(int, int)':
autobahn.cpp:235:20: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int, std::vector<int>, std::greater<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  235 |   while (pq.size() > k) pq.pop();
      |          ~~~~~~~~~~^~~
autobahn.cpp:237:17: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int, std::vector<int>, std::greater<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  237 |   if (pq.size() >= k){
      |       ~~~~~~~~~~^~~~
autobahn.cpp: In function 'void simplify()':
autobahn.cpp:249:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  249 |  while (p < ak.size()){
      |         ~~^~~~~~~~~~~
autobahn.cpp:253:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  253 |   while (P < ak.size() && ak[P].fi <= lim){
      |          ~~^~~~~~~~~~~
autobahn.cpp: In function 'int main()':
autobahn.cpp:375:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  375 |     for (int i = 1 ; i <= n ; i++)
      |     ^~~
autobahn.cpp:378:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  378 |  prepare(n,k);
      |  ^~~~~~~

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