Submission #1147412

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147412		koukirocks	Marathon Race 2 (JOI24_ho_t3)	C++20	7 / 100	8 ms	12104 KiB

Main

#include <bits/stdc++.h>
#define F first
#define S second
#define speed ios_base::sync_with_stdio(0);cin.tie(0)
#define all(x) x.begin()+1, x.end()

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

template<class T>
using vvector = vector<vector<T>>;

const ll oo = 0x3f3f3f3f3f3f3f3f;
const ll INF = 0x3f3f3f3f;

int main() {
    speed;
    ll n,l;
    cin>>n>>l;
    l++;
    vector<ll> w(l+1);
    vector<ll> pre(l+1);
    vector<ll> pp(l+1);
    ll mx=0,mn=INF;
    for (int i=1;i<=n;i++) {
        ll x;
        cin>>x;
        x++;
        w[x]++;
        mx=max(mx,x);
        mn=min(mn,x);
    }
    for (int i=1;i<=l;i++) {
        pre[i]=pre[i-1]+w[i];
        pp[i]=pp[i-1]+w[i]*i;
    }
    int q;
    cin>>q;
    while (q--) {
        ll s,e,t;
        cin>>s>>e>>t;
        s++;e++;
        ll nmn,nmx;
        if (e<s) {
            nmn=min(mn,e);
            nmx=max(mx,e);
        } else {
            nmn=min(mn,s);
            nmx=max(mx,e);
        }
        ll ans=min(
            pp[l]-pp[e]+(e-2*nmn)*(pre[l]-pre[e]) + pre[e]*e-pp[e] + nmx-s+nmx-nmn+e-nmn,
            pp[l]-pp[e-1]-e*(pre[l]-pre[e-1]) + (2*nmx-e)*pre[e-1] + s-nmn+nmx-nmn+nmx-e
        )+n;
        cout<<(ans<=t?"Yes":"No")<<"\n";
    }
    return 0;
}

• Subtask 1: 7 / 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