Submission #1105259

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105259		ThegeekKnight16	Fish 3 (JOI24_fish3)	C++17	100 / 100	443 ms	82652 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e12 + 10;
struct node
{
    int sum, minSum, minVal, maxVal, lz;

    node (int S = 0, int MS = 0, int minV = INF, int maxV = 0) : sum(S), minSum(MS), minVal(minV), maxVal(maxV), lz(-INF) {}

    node operator+ (node outro)
    {
        return node(sum + outro.sum, minSum + outro.minSum, min(minVal, outro.minVal), max(maxVal, outro.maxVal));
    }
};
const int MAXN = 3e5 + 10;
array<node, 4*MAXN> seg;

void refresh(int pos, int ini, int fim)
{
    if (seg[pos].lz == -INF) return;
    int x = seg[pos].lz;
    seg[pos] = node(seg[pos].sum, (fim-ini+1)*x, x, x);

    if (ini == fim) return;
    int e = 2*pos, d = e+1;
    seg[e].lz = seg[d].lz = x;
}

void update(int pos, int ini, int fim, int p, int q, int val)
{
    refresh(pos, ini, fim);
    if (q < ini || p > fim) return;
    if (p <= ini && fim <= q)
    {
        // cerr << val << " at " << ini << " " << fim << '\n';
        seg[pos].lz = val;
        refresh(pos, ini, fim);
        return;
    }
    int m = (ini + fim) >> 1;
    int e = 2*pos, d = e+1;
    update(e, ini, m, p, q, val);
    update(d, m+1, fim, p, q, val);
    seg[pos] = seg[e] + seg[d];
}

void build(int pos, int ini, int fim, const vector<int> &C, const vector<int> &S, int D)
{
    if (ini == fim)
    {
        seg[pos] = node((C[ini]/D)-S[ini]);
        return;
    }

    int m = (ini + fim) >> 1;
    int e = 2*pos, d = e+1;
    build(e, ini, m, C, S, D);
    build(d, m+1, fim, C, S, D);
    seg[pos] = seg[e] + seg[d];
}

node query(int pos, int ini, int fim, int p, int q)
{
    refresh(pos, ini, fim);
    if (q < ini || p > fim) return node();
    if (p <= ini && fim <= q) return seg[pos];
    int m = (ini + fim) >> 1;
    int e = 2*pos, d = e+1;
    return (query(e, ini, m, p, q) + query(d, m+1, fim, p, q));
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N, D;
    cin >> N >> D;
    vector<int> C(N+1);
    for (int i = 1; i <= N; i++) cin >> C[i];
    vector<int> S(N+1); for (int i = 2; i <= N; i++) S[i] = S[i-1] + (int)((C[i]%D) < (C[i-1]%D));
    // cerr << "S: "; for (int i = 1; i <= N; i++) cerr << S[i] << " "; cerr << '\n';
    build(1, 1, N, C, S, D);

    int Q; cin >> Q;
    vector<int> resp(Q); vector<vector<pair<int, int>>> queries(N+1);
    for (int i = 0; i < Q; i++)
    {
        int L, R;
        cin >> L >> R;
        queries[R].emplace_back(L, i);
    }

    stack<pair<int, int>> s; s.emplace(-INF, 0);
    for (int i = 1; i <= N; i++)
    {
        while (s.top().first >= (C[i]/D)-S[i]) s.pop();
        update(1, 1, N, s.top().second+1, i, (C[i]/D)-S[i]);
        s.emplace((C[i]/D)-S[i], i);

        for (auto [L, id] : queries[i])
        {
            auto ans = query(1, 1, N, L, i);
            // cerr << "L: " << L << ", R: " << i << ", sum: " << ans.sum << ", minSum: " << ans.minSum << ", minVal: " << ans.minVal << '\n';
            if (ans.minVal + S[L] < 0) resp[id] = -1;
            else resp[id] = ans.sum - ans.minSum;
        }
    }

    for (auto x : resp) cout << x << '\n';
}

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