Submission #1116133

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116133		hqminhuwu	Fish 3 (JOI24_fish3)	C++14	100 / 100	713 ms	71100 KiB

Main

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector <int> vi;
typedef pair <ll,ll> pll;
typedef pair <int,int> pii;
typedef pair <int,pii> piii;

#define forr(_a,_b,_c) for(int _a = (_b); _a <= int (_c); ++_a)
#define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> int (_c);)
#define forf(_a,_b,_c) for(int _a = (_b); _a < int (_c); ++_a)
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"

template<class X, class Y>
    bool minz(X &x, const Y &y) {
        if (x > y) {
            x = y;
            return true;
        } return false;
    }
template<class X, class Y>
    bool maxz(X &x, const Y &y) {
        if (x < y) {
            x = y;
            return true;
        } return false;
    }

const int N = 3e5 + 5;
const ll oo = (ll) 1e16;
const ll mod = 1e9 + 7; // 998244353;

int n, q, l, r;
ll d, a[N], tree[N << 2], lz[N << 2], fl[N], ans[N], mn[N << 2], lzmn[N << 2];
vector <pii> qq[N];

void down (int i, int l, int r){
    if (!lz[i]) return;
    int mid = l + r >> 1;
    tree[i << 1] += (mid - l + 1) * lz[i];
    tree[i << 1 | 1] += (r - mid) * lz[i];
    lz[i << 1] += lz[i];
    lz[i << 1 | 1] += lz[i];
    lz[i] = 0;
}

void downmn (int i){
    if (!lzmn[i]) return;
    forr (j, i << 1, i << 1 | 1){
        mn[j] += lzmn[i];
        lzmn[j] += lzmn[i];
    }
    lzmn[i] = 0;
}

void addmn (int i, int l, int r, int u, int v, ll val){
    if (l > v || r < u) return;
   // cout << l << " " << r << " " << val << endl;
    if (l >= u && r <= v){
        mn[i] += val;
        lzmn[i] += val;
        return;
    }
    downmn(i);
    int mid = l + r >> 1;
    addmn(i << 1, l, mid, u, v, val);
    addmn(i << 1 | 1, mid + 1, r, u, v, val);
    mn[i] = min (mn[i << 1], mn[i << 1 | 1]);
}

ll getmn (int i, int l, int r, int u, int v){
    if (l > v || r < u) return mod;
    if (l >= u && r <= v) return mn[i];
    downmn(i);
    int mid = l + r >> 1;
    return min(getmn(i << 1, l, mid, u, v), getmn(i << 1 | 1, mid + 1, r, u, v));
}

void add (int i, int l, int r, int u, int v, ll val){
    if (l > v || r < u) return;
    if (l >= u && r <= v){
        tree[i] += (r - l + 1) * val;
        lz[i] += val;
        return;
    }
    down(i, l, r);
    int mid = l + r >> 1;
    add(i << 1, l, mid, u, v, val);
    add(i << 1 | 1, mid + 1, r, u, v, val);
    tree[i] = tree[i << 1] + tree[i << 1 | 1];
}

void add (int l, int r, ll val){
    add(1, 1, n, l, r, val);
}

ll get (int i, int l, int r, int u, int v){
    if (l > v || r < u) return 0;
    if (l >= u && r <= v) return tree[i];
    down(i, l, r);
    int mid = l + r >> 1;
    return get(i << 1, l, mid, u, v) + get(i << 1 | 1, mid + 1, r, u, v);
}

ll get (int u){
    return get(1, 1, n, u, u);
}

ll get (int l, int r){
    return get(1, 1, n, l, r);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifdef kaguya
        freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
    #endif

    cin >> n >> d;

    forr (i, 1, n){
        cin >> a[i];
    }

    cin >> q;

    forr (i, 1, q){
        cin >> l >> r;
        qq[r].pb({l, i});
    }


    forr (i, 1, n){
        fl[i] = i;
        addmn(1, 1, n, i, i, a[i]);
        if (i != 1){
            ll cur = i;
            while (1){
                ll tmp = a[cur - 1] - d  * get(cur - 1) - (a[cur] - d * get(cur));
               // cout << cur << " " << fl[cur] << " " << tmp << endl;
                if (tmp <= 0 || fl[cur] == 1) break;
                add(fl[fl[cur] - 1], fl[cur] - 1, (tmp - 1) / d + 1); 
                addmn(1, 1, n, fl[fl[cur] - 1], fl[cur] - 1, -((tmp - 1) / d + 1) * d);
                fl[cur] = fl[fl[cur] - 1];
               // cout << cur << " " << fl[cur] << " " << tmp << "---\n";
                cur = fl[cur];
            }
            fl[i] = fl[cur];
        }
        for (pii u : qq[i]){
            if (getmn(1, 1, n, u.st, i) < 0) ans[u.nd] = -1;
            else ans[u.nd] = get(u.st, i);
        }
        // forr (j, 1, i){
        //     cout << getmn(1, 1, n, j, j) << " ";
        // }
        // cout << "\n";
        // cout << "=========\n";
    }

    forr (i, 1, q){
        cout << ans[i] << "\n";
    }


    return 0;
}
/*



*/

Compilation message (stderr)

Main.cpp: In function 'void down(int, int, int)':
Main.cpp:48:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |     int mid = l + r >> 1;
      |               ~~^~~
Main.cpp: In function 'void addmn(int, int, int, int, int, ll)':
Main.cpp:74:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |     int mid = l + r >> 1;
      |               ~~^~~
Main.cpp: In function 'll getmn(int, int, int, int, int)':
Main.cpp:84:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |     int mid = l + r >> 1;
      |               ~~^~~
Main.cpp: In function 'void add(int, int, int, int, int, ll)':
Main.cpp:96:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   96 |     int mid = l + r >> 1;
      |               ~~^~~
Main.cpp: In function 'll get(int, int, int, int, int)':
Main.cpp:110:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  110 |     int mid = l + r >> 1;
      |               ~~^~~

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