Submission #1183993

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183993		jerzyk	Dungeon 3 (JOI21_ho_t5)	C++20	100 / 100	460 ms	112304 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 10LL;
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1<<18;
int rmq[N][20];

int jp[N][20], jpl[N][20];
ll jps[N][20];

ll dis[N], sump[N], cst[N];
int l[N], r[N];
vector<int> cq;


ll drz[2 * N], laz[2 * N], il[2 * N];

pair<ll, int> que[N];
pair<int, int> ran[N];
ll answer[N];
int cnt[N];

pair<int, ll> Jump(int a, ll d)
{
    int st = a;
    ll s = 0LL;
    //cerr << "J " << d << "\n";
    for(int i = 18; i >= 0; --i)
        if(sump[jp[a][i] - 1] - sump[st - 1] <= d)
        {
            //cerr << "j: " << a << " " << "\n";
            s += jps[a][i];
            a = jp[a][i];
        }
    return make_pair(a, s);
}

int JP2(int a, ll d)
{
    int st = a;
    for(int i = 18; i >= 0; --i)
        if(sump[st] - sump[jpl[a][i] - 1] <= d)
            a = jpl[a][i];
    return a;
}

int MaQue(int a, int b)
{
    int r = 31 - __builtin_clz(b - a + 1);
    return max(rmq[a][r], rmq[b - (1<<r) + 1][r]);
}

inline void Push(int v)
{
    for(int nv = v * 2; nv <= v * 2 + 1; ++nv)
    {
        drz[nv] += laz[v] * il[nv];
        laz[nv] += laz[v];
    }
    laz[v] = 0;
}

void Change(int v, int val)
{
    int x = 1;
    for(int i = 17; i >= 0; --i)
    {
        Push(x);
        x *= 2;
        if(v & (1<<i)) ++x;
    }
    il[x] += val;
    x /= 2;
    while(x > 0)
    {
        il[x] = il[x * 2] + il[x * 2 + 1];
        x /= 2;
    }
}

ll Query(int v, int p, int k, int pz, int kz)
{
    if(p > kz || k < pz) return 0LL;
    if(p >= pz && k <= kz) return drz[v];
    Push(v);
    ll a;
    a = Query(v * 2, p, (p + k) / 2, pz, kz);
    a += Query(v * 2 + 1, (p + k) / 2 + 1, k, pz, kz);
    return a;
}

void Upd(ll x)
{
    drz[1] += il[1] * x;
    laz[1] += x;
}

void DoQ(int n, int q)
{
    vector<pair<ll, int>> cha;
    ll lst = 0LL;
    for(int i = 1; i <= n; ++i)
    {
        cnt[i] = 0;
        ll d1 = sump[r[i] - 1] - sump[i - 1];
        ll d2 = I;
        if(l[i] != 0)
            d2 = sump[i - 1] - sump[l[i] - 1];
        //cout << i << " l: " << l[i] << " " << d2 << " r: " << r[i] << " " << d1 << "\n";
        cha.pb(make_pair(d1, i));
        cha.pb(make_pair(d2, i));
        cha.pb(make_pair(d1 + d2, i));
    }
    //cerr << "xd\n";
    sort(cha.begin(), cha.end());
    int j = 0;
    for(int i = 1; i <= q; ++i)
    {
        int p = ran[que[i].nd].st, k = ran[que[i].nd].nd;
        while(j < (int)cha.size() && (ll)que[i].st >= cha[j].st)
        {
            //cout << "Cha: " << cha[j].st << "\n"
            Upd(cha[j].st - lst);
            lst = cha[j].st;
            if(cnt[cha[j].nd] < 2)
                Change(cha[j].nd, -cst[cha[j].nd]);
            else
                Change(cha[j].nd, cst[cha[j].nd]);
            ++cnt[cha[j].nd];
            ++j;
        }
        Upd(que[i].st - lst);
        lst = que[i].st;
        int xd = MaQue(p, k - 1);
        if(que[i].st >= xd)
        {
            ll ans = 0LL;
            pair<int, ll> xd;
            xd = Jump(p, min((ll)que[i].st, sump[k - 1] - sump[p - 1]));
            int cur = xd.st;
            int cur2 = JP2(k - 1, min((ll)que[i].st, sump[k - 1] - sump[cur - 1]));
            if(cur2 < cur) cur2 = cur;
            ans = xd.nd;
            //cerr << "S: " << ans << " " << cur << " " << cur2 << " " << jpl[cur2][0] << "\n";
            //cur2 = l[cur2];
            if(cur != cur2)
            {
                ll mn = min(min((ll)que[i].st, sump[k - 1] - sump[cur - 1]), sump[r[cur] - 1] - sump[cur - 1]);
                ans += mn * cst[cur];
            }

            if(cur2 != k)
            {
                ll mn = sump[k - 1] - sump[cur2 - 1];
                ll df = 0LL;
                if(l[cur2] >= p)
                    df = max(0LL, min(que[i].st, sump[k - 1] - sump[l[cur2] - 1]) - (sump[cur2 - 1] - sump[l[cur2] - 1]));
                mn -= df;
                ans += mn * cst[cur2];
            }
            //cerr << ans << "\n";
            if(cur + 1 <= cur2 - 1)
                ans += Query(1, 0, N - 1, cur + 1, cur2 - 1);
            //cerr << i << " " << cur << " " << ans << "\n";
            answer[que[i].nd] = ans;
        }
        else
            answer[que[i].nd] = -1;
    }
}

void Solve()
{
    int n, q;
    cin >> n >> q;
    for(int i = 1; i <= n; ++i)
    {
        cin >> dis[i];
        rmq[i][0] = dis[i];
        sump[i] = sump[i - 1] + dis[i];
    }
    //cerr << "xd\n";
    for(int i = n; i >= 1; --i)
        for(int j = 1; i + (1<<j) - 1 <= n; ++j)
            rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1<<(j - 1))][j - 1]);
    //cerr << "xd\n";
    cst[0] = -II;
    cq.pb(0);
    for(int i = 1; i <= n; ++i)
    {
        cin >> cst[i]; il[i + N] = cst[i];
        while(cst[cq.back()] > cst[i])
            cq.pop_back();
        l[i] = cq.back();
        jpl[i][0] = l[i];
        cq.pb(i);
    }
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= 18; ++j)
            jpl[i][j] = jpl[jpl[i][j - 1]][j - 1];
    for(int i = N - 1; i >= 1; --i) il[i] = il[i * 2] + il[i * 2 + 1];
    cq.clear();
    cst[n + 1] = -II;
    cq.pb(n + 1);
    //cerr << "xd\n";
    for(int i = n; i >= 1; --i)
    {
        while(cst[cq.back()] >= cst[i])
            cq.pop_back();
        r[i] = cq.back();
        cq.pb(i);
        jp[i][0] = r[i];
        jps[i][0] = (sump[r[i] - 1] - sump[i - 1]) * cst[i];
    }
    jp[n + 1][0] = n + 1;
    for(int i = n + 1; i >= 1; --i)
        for(int j = 1; j <= 18; ++j)
        {
            jp[i][j] = jp[jp[i][j - 1]][j - 1];
            jps[i][j] = jps[i][j - 1] + jps[jp[i][j - 1]][j - 1];
        }
    for(int i = 1; i <= q; ++i)
    {
        cin >> ran[i].st >> ran[i].nd;
        cin >> que[i].st;
        que[i].nd = i;
    }
    sort(que + 1, que + 1 + q);
    DoQ(n, q);
    for(int i = 1; i <= q; ++i)
        cout << answer[i] << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    Solve();

    return 0;
}

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