Submission #1263204

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263204		earlyamazon	Dungeon 3 (JOI21_ho_t5)	C++20	100 / 100	371 ms	70076 KiB

Main

#pragma GCC diagnostic ignored "-Wunused-parameter"
#pragma GCC diagnostic ignored "-Wunused-variable"
#pragma GCC diagnostic ignored "-Wshadow"
#pragma GCC diagnostic ignored "-Wconversion"
#pragma GCC diagnostic ignored "-Wsign-compare"

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll mn = 2e5+7;
const ll oo = 1e18+7;
ll n,q;
ll lewo[mn], prawo[mn], A[mn], B[mn], x[mn], L[mn], R[mn], wynik[mn], U[mn], prefu[mn], prefsum[mn], ost[mn], wpref[mn];
pair<ll,ll> kol[mn];

struct node{
    ll a=0, b=0, mx=0;
    pair<ll,ll> najm;
};

node d[mn*2];

void merge(ll ind){
    d[ind].a = d[ind*2].a + d[ind*2+1].a;
    d[ind].b = d[ind*2].b + d[ind*2+1].b;
}

void update(ll ind){
    ind += mn;
    while (ind /= 2) merge(ind);
}

pair<ll,ll> read(ll l, ll r, ll u){
    ll suma = 0;
    ll sumb = 0;
    pair<ll,ll> n = {oo, oo};
    for (l += mn, r += mn+1; l < r; l/=2, r/=2){
        if (l&1){
            // cerr<<"x\n";
            n = min(n, d[l].najm);
            suma += d[l].a;
            sumb += d[l++].b;
        }
        if (r&1){
            // cerr<<"y\n";
            suma += d[--r].a;
            sumb += d[r].b;
            n = min(n, d[r].najm);
        }
    }
    return {suma*u+sumb, -n.second};
}

ll maks(ll l, ll r){
    ll w = 0;
    for (l += mn, r += mn+1; l < r; l/=2, r/=2){
        if (l&1) w = max(w, d[l++].mx);
        if (r&1) w = max(w, d[--r].mx);
    }
    return w;
}

// moze do n zamiast q
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>q;
    for (int i = 0; i < mn*2; i++){
        d[i].najm = {oo,oo};
    }
    for (ll i = 1; i <= n; i++){
        cin>>A[i];
        x[i+1] = x[i]+A[i];
    }
    x[n+2] = oo/10;
    x[0] = -oo/10;
    for (ll i = 1; i <= n; i++){
        cin>>B[i];
    }
    vector<ll> stos = {1};
    for (ll i = 2; i <= n; i++){
        while (!stos.empty() && B[stos.back()]>=B[i]){
            prawo[stos.back()] = i;
            stos.pop_back();
        }
        stos.push_back(i);
    }
    for (auto i : stos){
        prawo[i] = n+1;
    }
    stos.clear();
    stos = {n};
    for (ll i = n-1; i; i--){
        while (!stos.empty() && B[stos.back()]>B[i]){
            lewo[stos.back()] = i;
            stos.pop_back();
        }
        stos.push_back(i);
    }
    for (auto i : stos){
        lewo[i] = 0;
    }
    // for (ll i = 1; i <= n; i++){
    //     cout<<lewo[i]<<" "<<prawo[i]<<"\n";
    // }
    // cout<<"\n";
    vector<pair<ll,pair<ll,ll>>> wyd;
    for (ll i = 1; i <= n; i++){
        ll dl = x[i] - x[lewo[i]];
        ll dr = x[prawo[i]] - x[i];
        // cout<<"i: "<<i<<" "<<dl<<" "<<dr<<"\n";
        wyd.push_back({min(dl, dr), {1,i}});
        wyd.push_back({max(dl, dr), {2,i}});
        wyd.push_back({max(dl,dr)+min(dl,dr), {3,i}});
        d[i+mn].a = B[i];
        d[i+mn].najm = {B[i], -i};
        d[i+mn].mx = A[i];
    }
    // d[n+1+mn].najm = {}
    for (ll i = mn-1; i; i--){
        d[i].a = d[i*2].a + d[i*2+1].a;
        d[i].najm = min(d[i*2].najm, d[i*2+1].najm);
        d[i].mx = max(d[i*2].mx, d[i*2+1].mx);
    }
    vector<pair<ll,ll>>zap;
    for (ll i = 1; i <= q; i++){
        ll l,r,u;
        cin>>l>>r>>u;
        wyd.push_back({u, {0, i}});
        L[i] = l;
        R[i] = r;
        U[i] = u;
        zap.push_back({l, i});
    }
    sort(zap.begin(), zap.end(), greater<pair<ll,ll>>());
    sort(wyd.begin(), wyd.end());
    // for (auto i : zap){
    //     cout<<"zap: "<<i.first<<" "<<i.second<<"\n";
    // }
    ll ind = 0, wsk=0;
    for (ll i = n; i; i--){
        // cout<<"i: "<<i<<"\n";
        if (!wsk) kol[wsk++] = {B[i],i};
        else{
            while (wsk && kol[wsk-1].first > B[i]) wsk--;
            if (wsk){
                prefu[wsk] = prefu[wsk-1] + x[kol[wsk-1].second]-x[i];
                prefsum[wsk] = prefsum[wsk-1] + (x[kol[wsk-1].second]-x[i])*B[i];
            }
            kol[wsk++] = {B[i], i};
        }
        // for (ll j = 0; j < wsk; j++){
        //     cout<<kol[j].first<<" ";
        // }
        // cout<<"\n";
        // for (ll j = 0; j < wsk; j++){
        //     cout<<kol[j].second<<" ";
        // }
        // cout<<"\n";
        // for (ll j = 0; j < wsk; j++){
        //     cout<<prefu[j]<<" ";
        // }
        // cout<<"\n";
        // for (ll j = 0; j < wsk; j++){
        //     cout<<prefsum[j]<<" ";
        // }
        // cout<<"\n";
        while (ind < q && zap[ind].first == i){
            // cout<<"aaaaaaaaaaaaaaa\n";
            ll l = i, r = R[zap[ind].second], u = U[zap[ind].second];
            ll pocz = 0, kon = wsk-1, sr, wyn=0;
            while (pocz <= kon){
                sr = (pocz+kon)/2;
                // cout<<"sr: "<<sr<<" "<<prefu[wsk-1]<<" "<<prefu[sr]<<"\n";
                if (prefu[wsk-1]-prefu[sr] > u){
                    pocz = sr+1;
                }
                else{
                    kon = sr-1;
                    wyn = sr;
                }
            }
            // cout<<"wsk: "<<wsk<<" "<<wyn<<"\n";
            ll w1 = wyn;
            pocz = 0;
            kon = wsk-1;
            while (pocz <= kon){
                sr = (pocz+kon)/2;
                if (kol[sr].second > r){
                    pocz = sr+1;
                }
                else{
                    kon = sr-1;
                    wyn = sr;
                }
            }
            wyn = max(w1, wyn);
            ost[zap[ind].second] = kol[wyn].second;
            wpref[zap[ind].second] = prefsum[wsk-1] - prefsum[wyn];
            // cout<<"WYNIK: "<<wyn<<" "<<ost[zap[ind].second]<<" "<<wpref[zap[ind].second]<<"\n";
            ind++;
        }
        // cout<<"\n";
    }
    // cout<<"ostwpref:\n";
    // for (ll i = 1; i <= q; i++){
    //     cout<<ost[i]<<" "<<wpref[i]<<"\n";
    // }
    // cerr<<"aAAAAAAAAAA\n";
    // return 0;
    // cerr<<"wyd\n";
    // for (auto i : wyd){
    //     cerr<<i.first<<" "<<i.second.first<<" "<<i.second.second<<"\n";
    // }
    // cerr<<"\n\n";
    for (auto i : wyd){
        if (i.first > oo/100) break;
        // cout<<i.first<<" "<<i.second.first<<" "<<i.second.second<<"\n";
        if (i.second.first == 1){
            d[i.second.second+mn].a = 0;
            d[i.second.second+mn].b = i.first*B[i.second.second];
            update(i.second.second);
        }
        else if (i.second.first == 2){
            d[i.second.second+mn].a = -B[i.second.second];
            d[i.second.second+mn].b += i.first*B[i.second.second];
            update(i.second.second);
        }
        else if (i.second.first == 3){
            d[i.second.second+mn].a = 0;
            d[i.second.second+mn].b = 0;
            update(i.second.second);
        }
        else{
            // ll l = L[i.second.second];
            ll l = ost[i.second.second];
            ll r = R[i.second.second];
            ll u = i.first;
            // cerr<<"lr: "<<l<<" "<<r<<"\n";
            // cout<<"maks: "<<maks(l, r-1)<<"\n";
            if (maks(l, r-1) > u) wynik[i.second.second] = -1;
            else{
                ll w = wpref[i.second.second];
                if (l < r){
                    // for (ll j = 1; j <= n; j++){
                    //     cout<<"j: "<<j<<" "<<d[j+mn].a<<" "<<d[j+mn].b<<" "<<u*d[j+mn].a+d[j+mn].b<<"\n";
                    // }
                    // cout<<"w: "<<w<<" ";
                    int ilewl = min(min(x[prawo[l]]-x[l],u), x[r]-x[l]);
                    w += ilewl*B[l];
                    // cout<<w<<" ";
                    ll pocz = l, kon = r-1, sr, wyn=0;
                    while (pocz <= kon){
                        sr = (pocz+kon)/2;
                        // cerr<<"rx "<<x[sr]<<" "<<x[r]<<"\n";
                        if (x[r]-x[sr] > u){
                            pocz = sr+1;
                        }
                        else{
                            wyn = sr;
                            kon = sr-1;
                        }
                    }
                    pair<ll, ll> p = {0,0};
                    p = read(wyn, r-1, u);
                    // r = p.second;
                    auto p2 = read(l+1, p.second, i.first);
                    w += p2.first;
                    // cout<<w<<"\n";
                    // cout<<p.first<<" "<<p.second<<"\n";
                    // w -= max(0LL, (x[prawo[p.second]]-x[r])*B[p.second]);
                    // cerr<<pocz<<" "<<kon<<"\n";
                    // cerr<<wyn<<" "<<r<<" "<<p.second<<"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAa\n";
                    if (p.second != l){
                        // if (x[p.second] - x[l] <= ilewl){
                        //     int start = ilewl - (x[p.second] - x[l]);
                        //     x[r]-x[p.second]-start
                        // }
                        w -= min(u, x[prawo[p.second]] - x[p.second])*B[p.second];
                        // cout<<w<<" ";
                        w += min(u, x[r]-x[p.second])*B[p.second];
                        // cout<<w<<"\n";
                        // cerr<<w<<"\n";
                        // cout<<"pom: "<<min(u, x[prawo[p.second]] - x[p.second])<<" "<<min(u, x[r]-x[p.second])<<"\n";
                        // cout<<"wyn: "<<wyn<<" "<<p.second<<"\n";
                        // cout<<"wynik: "<<w<<"\n";
                    }
                }
                wynik[i.second.second] = w;
            }
        }
    }
    for (ll i = 1; i <= q; i++){
        cout<<wynik[i]<<"\n";
    }
}

• Subtask 1: 11 / 11
• Subtask 2: 14 / 14
• Subtask 3: 31 / 31
• Subtask 4: 44 / 44