Submission #1147418

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147418		koukirocks	Marathon Race 2 (JOI24_ho_t3)	C++20	7 / 100	13 ms	19960 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;
    }
    vector<ll> lft(l+2),rt(l+2);
    for (int i=1;i<=l;i++) {
        lft[i]=(w[i]?i:lft[i-1]);
    }
    rt[l+1]=l+1;
    for (int i=l;i>=1;i--) {
        rt[i]=(w[i]?i:rt[i+1]);
    }
    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,s);
        } 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]-pp[e-1] + s-nmn+nmx-nmn+nmx-e,
        });
        // cout<<pp[l]-pp[e]+(e-2*nmn)*(pre[l]-pre[e]) + pre[e]*e-pp[e] + nmx-s+nmx-nmn+e-nmn<<" c1\n";
        // cout<<pp[l]-pp[e-1]-e*(pre[l]-pre[e-1]) + (2*nmx-e)*pre[e-1]-pp[e-1] + s-nmn+nmx-nmn+nmx-e<<" c2\n";
        if (e<s) {
            ll mmx=max(e,lft[s]);
            ans=min(ans,pp[l]-pp[s]+(2*mmx-2*nmn-e)*(pre[l]-pre[s]) + pp[s]-pp[e-1]-e*(pre[s]-pre[e-1]) + (2*mmx-e)*pre[e-1]-pp[e-1] + nmx-s+nmx-nmn+mmx-nmn+mmx-e);
            // cout<<pp[l]-pp[s]+(2*mmx-2*nmn-e)*(pre[l]-pre[s]) <<" "<< pp[s]-pp[e-1]-e*(pre[s]-pre[e-1]) <<" "<< (2*mmx-e)*pre[e-1]-pp[e-1] <<" "<< nmx-s+nmx-nmn+mmx-nmn+mmx-e<<" c3\n";
        } else {
            ll mmn=min(rt[s],e);
            ans=min(ans,pp[l]-pp[e]+(e-2*mmn)*(pre[l]-pre[e]) + (2*nmx-2*mmn+e)*pre[s-1]-pp[s-1] + e*(pre[e]-pre[s-1])-(pp[e]-pp[s-1]) + s-nmn+nmx-nmn+nmx-mmn+e-mmn);
            // cout<<pp[l]-pp[e]+(e-2*mmn)*(pre[l]-pre[e]) + (2*nmx-2*mmn+e)*pre[s-1]-pp[s-1] + e*(pre[e]-pre[s-1])-(pp[e]-pp[s-1]) + s-nmn+nmx-nmn+nmx-mmn+e-mmn<<" c3\n";
        }
        cout<<(ans+n<=t?"Yes":"No")<<"\n";
        // cout<<ans+n<<"\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