Submission #1012852

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012852		underwaterkillerwhale	Fish 3 (JOI24_fish3)	C++17	0 / 100	283 ms	129664 KiB

Main

#include <bits/stdc++.h>
#define se              second
#define fs              first
#define mp              make_pair
#define pb              push_back
#define ll              long long
#define ii              pair<ll,ll>
#define ld              long double
#define SZ(v)           (int)v.size()
#define ALL(v)          v.begin(), v.end()
#define bit(msk, i)     ((msk >> i) & 1)
#define iter(id, v)     for(auto id : v)
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r)
{
    return uniform_int_distribution<ll> (l, r)(rd);
}

const int N  = 3e5 + 7;
const int Mod = 998244353;
const int szBL = 916;
const ll INF = 1e9;
const int BASE = 137;

int n, Q;
ll D;
ll a[N];
pair<ll, ll> spt[N][25];

//struct Segment_Tree {
//    struct Node {
//        ll S, X, Size, L, R;
//    }st[N << 2];
//
//    void Merge (Node &cur, Node &lf, Node &rt) {
//        cur.R = rt.R;
//        if (rt.L > lf.R) {
//            cur.L = lf.L;
//            cur.S = lf.S + rt.S;
//            cur.X = lf.X;
//            cur.Size = lf.Size;
//        }
//        else {
//            cur.S = ceil(1.0 * (lf.R - rt.L) / D) + lf.X * rt.Size + rt.S + lf.S;
//            cur.X = lf.X + rt.X;
//            cur.Size =
//
//        }
//    }
//    void build (int id, int l, int r) {
//
//    }
//};

void solution() {
    cin >> n >> D;
    rep (i, 1, n) {
        cin >> a[i];
    }
//    ST.init(n);
    for (int j = 1; (1 << j) <= n; ++j) {
        for (int i = 1; i + (1 << j) - 1 <= n; i ++) {
            pair<ll, ll> &cur = spt[i][j], &lf = spt[i][j - 1], &rt = spt[i + (1 << j - 1)][j - 1];
            ll sz = (1 << j - 1);
//            if (i == 1 && j == 2) {
//                cout << lf.fs<<","<<lf.se<<" "<<rt.fs<<","<<rt.se <<"\n";
//            }
            cur.fs = lf.fs + rt.fs + rt.se * sz + sz * ceil (1.0 * (a[i + sz - 1] - a[i + sz]) / D);
            cur.se = lf.se + rt.se + ceil(1.0 * (a[i + sz - 1] - a[i + sz]) / D) ;
//            if (i == 1 && j == 2) {
//                cout << cur.fs <<" "<<cur.se<<" " <<lf.fs + rt.fs + rt.se * sz<<"\n";
//            }
        }
    }
//    cout << spt[1][2].fs <<"\n";
//    return;
    ll Q;
    cin >> Q;
    rep (q, 1, Q) {
        int L, R;
        cin >> L >> R;
        int st = L;
        ll S = 0, X = 0;
        reb (i, 20, 0) {
            if (st + (1 << i) - 1 <= R) {
                S = S + (st - L) * spt[st][i].se + spt[st][i].fs;
                X += spt[st][i].se;
                if (st > L) {
                    S = S + (st - L) *ceil(1.0 * (a[st - 1] - a[st]) / D);
                    X += ceil(1.0 * (a[st - 1] - a[st]) / D);
                }
                st += (1 << i);
            }
        }
//        cout << a[L] <<" "<< X<<"\n";
        if (a[L] - D * X < 0) {
            cout << -1 <<"\n";
        }
        else
            cout << S <<"\n";
    }
}


#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);
int main () {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
//    file ("WATERMOV");
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--)
        solution();
}
/*
6 4
18 16 12 8 5 3
3
1 4
1 5
2 4
1 4
5
6 7
4 9
1 5
1 5
8 9
*/

Compilation message (stderr)

Main.cpp: In function 'void solution()':
Main.cpp:70:87: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   70 |             pair<ll, ll> &cur = spt[i][j], &lf = spt[i][j - 1], &rt = spt[i + (1 << j - 1)][j - 1];
      |                                                                                     ~~^~~
Main.cpp:71:29: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   71 |             ll sz = (1 << j - 1);
      |                           ~~^~~

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