제출 #1057585

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1057585		beaconmc	Marathon Race 2 (JOI24_ho_t3)	C++14	0 / 100	6 ms	68444 KiB

Main

#include <bits/stdc++.h>
 
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
 
using namespace std;

const ll maxn = 500005;
const ll INF = 100000000000000000;
ll tree[maxn*4], tree2[maxn*4];
ll lazy[maxn*4], lazy2[maxn*4];

ll calc(ll k){
	return tree[k] + lazy[k];
}

void push(ll k){
	lazy[k*2] += lazy[k];
	lazy[k*2+1] += lazy[k];
	tree[k] += lazy[k];
	lazy[k] = 0;
}
void update(ll a, ll b, ll val, ll k=1, ll x=0, ll y=maxn-1){
	if (b<x || a>y) return;
	if (a<=x && y<=b){
		lazy[k] += val;
		return;
	}

	ll mid = (x+y)/2;
	push(k);
	update(a,b,val,k*2,x,mid);
	update(a,b,val,k*2+1,mid+1,y);

	tree[k] = min(calc(k*2), calc(k*2+1));
}

ll query(ll a, ll b, ll k=1, ll x = 0, ll y =maxn-1){
	if (b<x || a>y) return INF;
	if (a<=x && y<=b){
		return calc(k);
	}
	ll mid = (x+y)/2;
	push(k);

	return min(query(a, b, k*2, x, mid), query(a,b,k*2+1, mid+1, y));
}


ll calc2(ll k){
	return tree2[k] + lazy2[k];
}

void push2(ll k){
	lazy2[k*2] += lazy2[k];
	lazy2[k*2+1] += lazy2[k];
	tree2[k] += lazy2[k];
	lazy2[k] = 0;
}
void update2(ll a, ll b, ll val, ll k=1, ll x=0, ll y=maxn-1){
	if (b<x || a>y) return;
	if (a<=x && y<=b){
		lazy2[k] += val;
		return;
	}

	ll mid = (x+y)/2;
	push2(k);
	update2(a,b,val,k*2,x,mid);
	update2(a,b,val,k*2+1,mid+1,y);

	tree2[k] = min(calc2(k*2), calc2(k*2+1));
}

ll query2(ll a, ll b, ll k=1, ll x = 0, ll y =maxn-1){
	if (b<x || a>y) return INF;
	if (a<=x && y<=b){
		return calc2(k);
	}
	push2(k);
	ll mid = (x+y)/2;

	return min(query2(a, b, k*2, x, mid), query2(a,b,k*2+1, mid+1, y));
}


ll a,b,t, n, l;

ll arr[maxn];
ll pref[maxn];
ll suff[maxn];


ll dp(ll x, ll dir){
	if (dir==0){
		if (x==0) return INF;

		ll ans = 0;
		ans += pref[x-1];
		ans += (x+1)*abs(arr[x-1] - arr[n-1]);
		ans += suff[x] + abs(arr[n-1] - arr[x]) * (x);
		return ans;
	}else{
		if (x==n-1) return INF;
		ll ans = 0;
		ans += suff[x+1];
		ans += abs(n-1-x + 1) * abs(arr[0] - arr[x+1]);
		ans += pref[x] + abs(arr[0] - arr[x]) * abs(n-1-x);
		return ans;
	}
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	FOR(i,0,maxn*4) tree[i] = 0, lazy[i] = 0, tree2[i] = 0, lazy2[i] = 0;



	cin >> n >> l;

	FOR(i,0,n) cin >> arr[i];
	sort(arr, arr+n);
	ll cur = 1;
	ll pos = arr[0];
	ll tot = 0;
	FOR(i,0,n){
		ll diff = abs(pos-arr[i]);
		pos = arr[i];
		tot += diff * cur;
		cur++;
		pref[i] = tot;
	}

	cur = 1;
	pos = arr[n-1];
	tot = 0;
	FORNEG(i,n-1,-1){
		ll diff = abs(pos-arr[i]);
		pos = arr[i];
		tot += diff*cur;
		cur++;
		suff[i] = tot;
	}



	FOR(i,0,n){
		update(i, i, dp(i,0) + arr[i]*(n+1));
		update2(i, i, dp(i,1) + arr[i]*(n+1));
	}


	





	ll q;
	cin >> q;

	vector<vector<ll>> queries;

	FOR(i,0,q){
		cin >> a >> b >> t;
		queries.push_back({b, a, t, i});
	}
	sort(queries.begin(), queries.end());

	ll prev = 0;
	pos = 0;

	vector<string> ans(q);

	for (auto&i : queries){

		while (pos < n && arr[pos] <= i[0]){
			ll diff = abs(prev-arr[pos]);
			update(pos, n-1, -diff*(n+1));
			update2(pos, n-1, -diff*(n+1));
			if (pos != 0) update(0, pos-1, diff*(n+1));
			if (pos != 0) update2(0, pos-1, diff*(n+1));
			prev = arr[pos];
			pos++;
		}
		ll diff = abs(prev - i[0]);
		prev = i[0];
		update(pos, n-1, -diff*(n+1));
		update2(pos, n-1, -diff*(n+1));
		if (pos != 0) update(0, pos-1, diff*(n+1));
		if (pos != 0) update2(0, pos-1, diff*(n+1));

		ll temp = INF;

		temp = min(temp, query(0, n-1) + abs(i[1]-arr[0]));
		temp = min(temp, query2(0, n-1) + abs(i[1]-arr[n-1]));


		if (temp+n <= i[2]) ans[i[3]] = "Yes";
		else ans[i[3]] = "No";

	}
	for (auto&i : ans) cout << i << "\n";






}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 28
• Subtask 5: 0 / 10
• Subtask 6: 0 / 19
• Subtask 7: 0 / 19