Submission #1200173

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200173		janson0109	Fish 3 (JOI24_fish3)	C++20	100 / 100	668 ms	76032 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define f first
#define s second
using namespace std;
signed main() {
    int n, k; cin >> n >> k;
    vector<int> v(n+1), a(n+1), c(n+1);
    for(int i=0;i<n;i++) cin >> v[i+1];
    for(int i=n-1;i>0;i--) a[i] = max(0LL,(v[i]-v[i+1]+a[i+1]*k+k-1)/k);
    priority_queue<pair<int,int>> pq;
    a[0] = -1;
    for(int i=n;i>=0;i--) {
        pq.push({a[i],i});
        while(pq.top().f > a[i]) {c[pq.top().s] = i; pq.pop();}
    }
    vector<vector<int>> adj(n+1, vector<int>(19,-1));
    for(int i=0;i<=n;i++) adj[i][0] = c[i];
    for(int i=1;i<19;i++) for(int j=0;j<=n;j++) 
        adj[j][i] = adj[adj[j][i-1]][i-1];
    vector<int> p(n+1), q(n+1);
    for(int i=1;i<=n;i++) p[i] = p[c[i]] + a[i]*(i-c[i]), q[i] = q[i-1]+a[i];
    int _; cin >> _;
    while(_--) {
        int l, r; cin >> l >> r; int z = r;
        for(int i=18; i>=0; i--) if(adj[z][i] >= l) z = adj[z][i];
        if(v[l]-(a[l]-a[z])*k < 0) cout << "-1\n";
        else cout << q[r]-q[l-1]-(p[r]-p[z]+a[z]*(z-l+1)) << '\n';
    }
}

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