제출 #1253577

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1253577		nlsosad	Snowball (JOI21_ho_t2)	C++20	100 / 100	381 ms	39580 KiB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;
#define f first
#define s second
int a[200001];
int q[200001];
int pf[200001];
pair<int, int> le[200001], ri[200001];

struct segtree{
	int n;
	vector<int> tr;
	vector<int> lazy;
	segtree(int m){
		n = m;
		tr.resize(4*n + 5, 0);
		lazy.resize(4*n+5, 0);
	}
	void propa(int node, int l, int r){
		tr[node] += lazy[node];
		if(l!=r){
			lazy[2*node] += lazy[node];
			lazy[2*node+1] += lazy[node];
		}
		lazy[node] = 0;
	}
	void update(int node, int start, int end, int l, int r, int x){
		propa(node, start, end);
		if(l > end or r < start){
			return;
		}
		if(l<=start and end<=r){
			lazy[node] += x;
			propa(node, start, end);
			return;
		}
		int mid = (start+end)/2;
		update(2*node, start, mid, l, r, x);
		update(2*node+1, mid+1, end, l, r, x);
		tr[node] = max(tr[2*node], tr[2*node+1]);
	}
	int query(int node, int start, int end, int l, int r){
		propa(node, start, end);
		if(l > end or r < start){
			return 0;
		}
		if(l<=start and end<=r){
			return tr[node];
		}
		int mid = (start+end)/2;
		int t = query(2*node, start, mid, l, r);
		int p = query(2*node+1, mid+1, end, l, r);
		return max(t, p);
	}
	
};

int res[200001];
signed main(){
	int n, T;
	cin >> n >> T;
	for (int i = 1;i<=n;++i){
		cin >> a[i];
	}
	for (int i = 1;i<=T;++i){
		cin >> q[i];
	}
	sort(a+1, a+n+1);
	for (int i = 1;i<=T;++i){
		pf[i] = pf[i-1] + q[i];
	}
	for (int i = 1;i<=n;++i){
		if(i==1){
			le[i] = {1e18, i};
		}else le[i] = {a[i]-a[i-1], i};
	}
	for (int i = 1;i<=n;++i){
		if(i==n){
			ri[i] = {1e18, i};
		}else ri[i] = {a[i+1]-a[i], i};
	}
	sort(le+1, le+n+1);
	sort(ri+1, ri+n+1);
	segtree trai(n);
	segtree phai(n);
	int ml = 0, mr = 0;
	int trol = 1, tror = 1;
	for (int i = 1;i<=T;++i){
		if(pf[i]>=0){
			if(mr < pf[i]){
				mr = pf[i];
				int sum = ml+mr;
				int p = lower_bound(ri+1, ri+n+1, make_pair(sum, (int)-1)) - ri;
				int o = phai.query(1, 1, n, p, n);
				phai.update(1, 1, n, p, n, mr-o);
				while(tror<p){
					o = phai.query(1, 1, n, tror, tror);
					int des = ri[tror].f-ml;
					if(o < des){
						phai.update(1, 1, n, tror, tror, des-o);
						// cout << tror << " CAC\n";
						// cout << o << ' ' << des << '\n';
					}
					tror++;
				}
				// cout << mr-o << ' ';
				// cout << p << ' ' << sum << " NGU\n";
			}
		}else{
			if(ml < (-pf[i])){
				ml = -pf[i];
				int sum = ml+mr;
				int p = lower_bound(le+1, le+n+1, make_pair(sum, (int)-1)) - le;
				int o = trai.query(1, 1, n, p, n);
				trai.update(1, 1, n, p, n, ml-o);
				while(trol<p){
					o = trai.query(1, 1, n, trol, trol);
					int des = le[trol].f - mr;
					if(o < des){
						trai.update(1, 1, n, trol, trol, des-o);
						// cout << trol << " BUOI\n";
						// cout << o << ' ' << des << '\n';
					}
					trol++;
				}
				// cout << ml-o << ' ';
				// cout << p << ' ' << sum<<  " LON\n";
			}
		}
		// cout << ml << ' ' << mr << '\n';
	}
	for (int i = 1;i<=n;++i){
		// cout << i << '\n';
		int id = le[i].s;
		// cout << le[i].f << ' ' << le[i].s << ' ';
		// cout << ri[i].f << ' ' << ri[i].s << ' ';
		res[id] += trai.query(1, 1, n, i, i);
		// cout << trai.query(1, 1, n, i, i) << '\n';
		id = ri[i].s;
		res[id] += phai.query(1, 1, n, i, i);
		// cout << o << '\n';
	}
	for (int i = 1;i<=n;++i){
		cout << res[i] << '\n';
	}
}

• Subtask 1: 33 / 33
• Subtask 2: 67 / 67