Submission #1265523

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265523		Robert_junior	Marathon Race 2 (JOI24_ho_t3)	C++20	0 / 100	0 ms	320 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back  
#define all(x) x.begin(), x.end()
#define ins insert
#define F first
#define S second
const int N = 5e5 + 7, mod = 998244353;
int a[N], cnt[N];
void solve(){
	int n, len;
	cin>>n>>len;
	int x = 0;
	vector<int>v;
	for(int i = 1; i <= n; i++){
		cin>>a[i];
		cnt[a[i]]++;
		v.pb(a[i]);
	}
	sort(all(v));
	v.erase(unique(all(v)));
	int m = v.size();
	int q;
	cin>>q;
	while(q--){
		int s, t, k;
		cin>>s>>t>>k;
		if(m >= 1010){
			cout<<"NO\n";
			continue;
		}
		int res = 1e18;
		int sum = abs(s - v[0]), cur = 0;
		int lst = v[0];
		for(int i = 0; i < m; i++){
			sum += (cur + 1) * (v[i] - lst) + cnt[v[i]];
			cur += cnt[v[i]];
			int add = (v[m - 1] - v[i]) * (cur + 1), cur1 = cur, lst1 = v.back();
			for(int j = m - 1; j > i; j--){
				add += (cur1 + 1) * (lst1 - v[j]) + cnt[v[j]];
				cur1 += cnt[v[j]];
				lst1 = v[j];
			}
			lst = v[i];
			if(i == m - 1){
				add += abs(v[i] - t) * (n + 1);
			}
			else{
				add += abs(v[i + 1] - t) * (n + 1);
			}
			res = min(res, sum + add);
		}
		sum = abs(s - v[m - 1]), cur = 0, lst = v[m - 1];
		for(int i = m - 1; i >= 0; i--){
			sum += (cur + 1) * (v[i] - lst) + cnt[v[i]];
			cur += cnt[v[i]];
			int add = (v[i] - v[0]) * (cur + 1), cur1 = cur, lst1 = v[0];
			for(int j = 0; j < i; j++){
				add += (cur1 + 1) * (v[j] - lst1) + cnt[v[j]];
				cur1 += cnt[v[j]];
				lst1 = v[j];
			}
			if(i == 0){
				add += abs(v[0] - t) * (n + 1);
			}
			else{
				add += abs(v[i - 1] - t ) * (n + 1);
			}
			res = min(res, sum + add);
			lst = v[i];
		}
		//cout<<res<<'\n';
		if(res <= k){
			cout<<"YES\n";
		}
		else{
			cout<<"NO\n";
		}
	}
}
signed main(){
	ios_base :: sync_with_stdio(false);
	cin.tie(0);
    //freopen("area.in", "r", stdin);
    //freopen("area.out", "w", stdout);
    int t = 1;
    //cin>>t;
    while(t--){
        solve();
    }
}

• 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