제출 #1264612

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1264612		pocwicz	Dungeon 3 (JOI21_ho_t5)	C++17	100 / 100	689 ms	149548 KiB

Main

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

struct Zap{
    ll l;
    ll r;
    ll u;
    ll i;
};

struct Zm{
    ll u;
    ll helpV;
    ll i;
    ll a;
    ll b;
};

const ll LOG = 18;
const ll base = 1 << 18;
const ll INF = 1e9 + 1;
const ll MAXN = 2e5 + 7;
ll A[MAXN];
ll B[MAXN];
ll dist[MAXN];
ll dl[MAXN];
ll dr[MAXN];
ll whr[MAXN];
ll w[MAXN];
pair<ll, ll> treeW[base * 2];
pair<ll, ll> treeM[base * 2];
Zm zm[MAXN*3];
ll ans[MAXN];
ll sparse[MAXN][LOG];
ll logg[MAXN];
pair<ll, ll> jump[MAXN][LOG];
Zap zapyt[MAXN];
stack<pair<ll, pair<ll, ll>>> mon;

inline pair<ll, ll> dodajP(pair<ll, ll> a, pair<ll, ll> b){
    return {a.first+b.first, a.second+b.second};
}

pair<ll, ll> queryW(ll w, ll l, ll r, ll pocz, ll kon){
    if(r < pocz || kon < l){
        return {0, 0};
    }
    else if(pocz <= l && r <= kon){
        return treeW[w];
    }
    else{
        ll mid = (l+r)/2;
        ll left = w*2;
        ll right = w*2+1;
        return dodajP(queryW(left, l, mid, pocz, kon), queryW(right, mid+1, r, pocz, kon));
    }
}

void addW(ll w, pair<ll, ll> val){
    w += base-1;
    treeW[w] = val;
    w >>= 1;
    while(w != 0){
        treeW[w] = dodajP(treeW[w*2], treeW[w*2+1]);
        w >>= 1;
    }
}

pair<ll, ll> queryM(ll w, ll l, ll r, ll pocz, ll kon){
    if(r < pocz || kon < l){
        return {INF, 0};
    }
    if(pocz <= l && r <= kon){
        return treeM[w];
    }
    else{
        ll mid = (l+r)/2;
        ll left = w*2;
        ll right = w*2+1;
        return min(queryM(left, l, mid, pocz, kon), queryM(right, mid+1, r, pocz, kon));
    }
}

ll sparseRead(ll l, ll r){
    ll d = (r-l+1);
    ll k = logg[d];
    return max(sparse[l][k], sparse[r-(1<<k)+1][k]);
}

bool compZm(Zm a, Zm b){
    return (make_pair(a.u, a.helpV) < make_pair(b.u, b.helpV));
}

bool compZap(Zap a, Zap b){
    return a.u < b.u;
}

int32_t main(){
    for(ll i = 0 ; i < LOG ; i++){
        logg[(1 << i)] = i;
    }
    for(ll i = 1 ; i < MAXN ; i++){
        logg[i] = max(logg[i-1], logg[i]);
    }
    ll n, q;
    cin >> n >> q;

    for(ll i = 1; i <= n ; i++){
        cin >> A[i];
        dist[i+1] = dist[i]+A[i];
        sparse[i][0] = A[i];
    }
    for(ll d = 1 ; d < LOG ; d++){
        for(ll i = 1; i <= n ; i++){
            sparse[i][d] = max(sparse[i][d-1], sparse[min(n, i+(1 << (d-1)))][d-1]);
        }
    }
    for(ll i = 1; i <= n ; i++){
        cin >> B[i];
    }
    B[n+1] = INF;
    mon.push({0, {INF, -1}});
    for(ll i = 1 ; i <= n ; i++){
        pair<ll, pair<ll, ll>> akt = {B[i], {dist[i], i}};
        while(mon.top().first >= B[i]){
            mon.pop();
        }
        // cerr << i << " " << B[i] << " " << mon.top().first << " " << mon.top().second.second << " z\n";
        dl[i] = dist[i]-mon.top().second.first;
        if(mon.top().second.second == -1){
            dl[i] = INF;
        }
        mon.push(akt);
    }
    while(mon.top().first > 0){
        mon.pop();
    }
    for(ll i = n ; i > 0 ; i--){
        pair<ll, pair<ll, ll>> akt = {B[i], {dist[i], i}};
        while(mon.top().first > B[i]){
            mon.pop();
        }
        dr[i] = mon.top().second.first-dist[i];
        whr[i] = mon.top().second.second;
        if(mon.top().second.second == -1){
            dr[i] = INF;
            whr[i] = n+1;
        }
        mon.push(akt);
    }

    for(ll i = 1; i <= q ; i++){
        cin >> zapyt[i].l >> zapyt[i].r >> zapyt[i].u;
        zapyt[i].i = i;
    }

    ll zmit = 0;
    for(ll i = 1; i <= n+1 ; i++){
        // w[i] = max(0LL, min(min(u, dl[i]), min(dr[i], dl[i]+dr[i]-u)));
        if(i <= n){
            ll mn = min(dl[i], dr[i]);
            ll wk = max(dl[i], dr[i]);
            zm[++zmit] = {mn, 0, i, 0, mn*B[i]};
            zm[++zmit] = {wk, 1, i, -B[i], (dl[i]+dr[i])*B[i]};
            zm[++zmit] = {dl[i]+dr[i], 1, i, 0, 0};
        }
        treeW[i+base-1] = {B[i], 0};
        treeM[i+base-1] = {B[i], -i};
    }
    for(ll i = base-1 ; i > 0 ; i--){
        treeW[i] = dodajP(treeW[i*2],treeW[i*2+1]);
        treeM[i] = min(treeM[i*2], treeM[i*2+1]);
    }

    whr[n+1] = n+1;
    dr[n+1] = 0;
    for(ll i = 1; i <= n+1 ; i++){
        ll nast = whr[i];
        jump[i][0] = {whr[i], (dist[nast]-dist[i])*B[i]};
    }
    for(ll d = 1 ; d < LOG ; d++){
        for(ll i = 1; i <= n+1 ; i++){
            ll nk = jump[i][d-1].second+jump[jump[i][d-1].first][d-1].second;
            jump[i][d] = {jump[jump[i][d-1].first][d-1].first, nk};
        }
    }
    sort(zm+1, zm+1+zmit, compZm);
    zmit = 1;
    sort(zapyt+1, zapyt+1+q, compZap);

    // for(ll i = 1; i <= n ; i++){
    //     cerr << jump[i][0].first << " ";
    // }cerr << "\n";
    // for(ll i = 1; i <= n ; i++){
    //     cerr << jump[i][1].first << " ";
    // }cerr << "\n";
    // for(ll i = 1; i <= n ; i++){
    //     cerr << jump[i][2].first << " ";
    // }cerr << "\n";

    // for(ll i = 1; i <= n ; i++){
    //     cerr << w[i] << " ";
    // }cerr << "\n";
    // for(ll i = 1; i <= n ; i++){
    //     cerr << dl[i] << " ";
    // }cerr << "\n";
    // for(ll i = 1; i <= n ; i++){
    //     cerr << dr[i] << " ";
    // }cerr << "\n";

    for(ll ii = 1; ii <= q ; ii++){
        ll i = zapyt[ii].i;
        ll l = zapyt[ii].l;
        ll r = zapyt[ii].r;
        ll u = zapyt[ii].u;
        if(sparseRead(l, r-1) > u){
            ans[i] = -1;
            continue;
        }
        ll k = LOG-1;
        ll gdz = l;
        // cerr << gdz << " <<\n";
        ll limjp = min(u, dist[r]-dist[l]);
        while(k >= 0){
            if(dist[jump[gdz][k].first]-dist[l] <= limjp){ //
                ans[i] += jump[gdz][k].second;
                gdz = jump[gdz][k].first;
            }
            k--;
        }
        // cerr << ans[i] << " " << gdz << " przed prz\n";
        if(gdz == r){
            continue;
        }
        ans[i] += min(u, dr[gdz])*B[gdz];
        gdz++;
        // cerr << ans[i] << " " << gdz << " po prz\n";
        auto it = lower_bound(dist+1, dist+1+(n+1), dist[r]-u);
        ll whpoczfk = it-dist;
        ll whminr = -queryM(1, 1, base, max(l, whpoczfk), r).second;

        // cerr << whpoczfk << " " << whminr << " <<<\n";
        if(/*dist[r]-dist[gdz] >= u*/gdz <= whminr){
            while(zmit <= n*3 && zm[zmit].u < u){
                addW(zm[zmit].i, {zm[zmit].a, zm[zmit].b});
                zmit++;
            }
            // cerr << " faza srodkowa\n";
            pair<ll, ll> afunkcja = queryW(1, 1, base, gdz, whminr);
            ans[i] += afunkcja.first*u+afunkcja.second;
        }
        // faza koncowa
        ans[i] -= min(u, dr[whminr])*B[whminr];
        ans[i] += (dist[r]-dist[whminr])*B[whminr];
    }

    for(ll i = 1; i <= q ; i++){

        cout << ans[i] << "\n";
    }

    return 0;
}

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