Submission #1103755

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103755		vjudge1	Fish 3 (JOI24_fish3)	C++17	100 / 100	301 ms	65608 KiB

Main

#include<bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const ll maxn = 1e6 + 2, LG = 21, mod = 998244353, inf = 1e18;
ll n, d, c[maxn], q, l[maxn], r[maxn], fw_add[maxn], fw_mul[maxn], par[maxn], res[maxn];
vector<int> qr[maxn];
void upd (int idx, ll val)
{
    ll ok = -val*(idx - 1);
    while (idx <= n)
    {
        fw_add[idx] += ok;
        fw_mul[idx] += val;
        idx += (idx & (-idx));
    }
}
ll get (int idx)
{
    ll add = 0, mul = 0, i = idx;
    while (idx > 0)
    {
        add += fw_add[idx];
        mul += fw_mul[idx];
        idx -= (idx & (-idx));
    }
    return add + mul*i;
}
int find_set (int u)
{
    if (par[u] == u) return u;
    return (par[u] = find_set(par[u]));
}
void union_set (int u, int v)
{
    int pu = find_set(u), pv = find_set(v);
    par[pu] = pv;
}
int main ()
{
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> d;
    for (int i = 1; i <= n; i++)
    {
        cin >> c[i];
        par[i] = i;
    }
    cin >> q;
    for (int i = 1; i <= q; i++)
    {
        cin >> l[i] >> r[i];
        qr[r[i]].push_back(i);
    }
    for (int i = 1; i <= n; i++)
    {
        int u = i;
        while (u > 1)
        {
            ll x = c[u] - d * (get(u) - get(u - 1)), y = c[u - 1] - d * (get(u - 1) - get(u - 2));
            if (y <= x) break;
            union_set(u, u - 1);
            int l = find_set(u - 1);
            upd(l, (y - x + d - 1)/d);
            upd(u, -(y - x + d - 1)/d);
            u = l;
        }
        for (int j : qr[i])
        {
            if (c[l[j]] - d * (get(l[j]) - get(l[j] - 1)) < 0) res[j] = -1;
            else res[j] = get(i) - get(l[j] - 1);
        }
    }
    for (int i = 1; i <= q; i++) cout << res[i] << '\n';
}

• Subtask 1: 9 / 9
• Subtask 2: 7 / 7
• Subtask 3: 28 / 28
• Subtask 4: 20 / 20
• Subtask 5: 36 / 36