Submission #1181268

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181268		trashaccount	Fish 3 (JOI24_fish3)	C++20	100 / 100	348 ms	46972 KiB

Main

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

#define int long long
#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair

const int NM = 3e5;

struct node{
    int l, r, cl, cr;
};

int N, D, C[NM+5], Q;
vector <pii> arr[NM+5];
stack <node> S;
int st[4*NM+5], lazy[4*NM+5];
int ans[NM+5];

void down(int id, int l, int r){
    int mid = (l+r)/2;
    st[2*id] += lazy[id]*(mid-l+1); st[2*id+1] += lazy[id]*(r-mid);
    lazy[2*id] += lazy[id]; lazy[2*id+1] += lazy[id];
    lazy[id] = 0;
}

void update(int id, int l, int r, int u, int v, int val){
    if (v < l || u > r) return;
    if (l >= u && r <= v){
        st[id] += (r-l+1)*val;
        lazy[id] += val;
        return;
    }
    down(id, l, r);
    int mid = (l+r)/2;
    update(2*id, l, mid, u, v, val);
    update(2*id+1, mid+1, r, u, v, val);
    st[id] = st[2*id]+st[2*id+1];
}

int get(int id, int l, int r, int u, int v){
    if (v < l || u > r) return 0;
    if (l >= u && r <= v) return st[id];
    down(id, l, r);
    int mid = (l+r)/2;
    return get(2*id, l, mid, u, v)+get(2*id+1, mid+1, r, u, v);
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> D;
    for (int i = 1; i <= N; i++) cin >> C[i];

    cin >> Q;
    for (int i = 1; i <= Q; i++){
        int l, r; cin >> l >> r;
        arr[r].push_back(mp(l, i));
    }
    for (int i = 1; i <= N; i++){
        int cur = C[i], j = i;
        while (!S.empty()){
            node tmp = S.top();
            if (tmp.cr <= cur) break;
            S.pop();
            int num = (tmp.cr-cur+D-1)/D;
            update(1, 1, N, tmp.l, tmp.r, num);
            
            cur = tmp.cl-num*D, j = tmp.l;
        }
        S.push(node{j, i, cur, C[i]});

        for (pii p : arr[i]){
            int j = p.fi, id = p.se;
            if (C[j]-get(1, 1, N, j, j)*D < 0){
                ans[id] = -1;
                continue;
            }
            ans[id] = get(1, 1, N, j, i);
        }
    }
    for (int i = 1; i <= Q; i++) cout << ans[i] << '\n';
    return 0;
}

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