oj.uz

답안 #1012838

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1012838 2024-07-02T16:50:40 Z underwaterkillerwhale Fish 3 (JOI24_fish3) C++17
0 / 100
 279 ms 126768 KB 

#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];
            int 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 +
                    1LL * ceil(1.0 * (a[i + sz - 1] - a[i + sz] + rt.se) / D) * sz;
            cur.se = lf.se + rt.se + ceil(1.0 * (a[i + sz - 1] - a[i + sz] + rt.se) / D) ;
        }
    }
//    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 + ceil(1.0 * (a[st - 1] - a[st] + spt[st][i].se) / D);
                    X += ceil(1.0 * (a[st - 1] - a[st] + spt[st][i].se) / 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 6 4
2 2 3 6
2 2 6 3
2 4 4 5
4 2 6 4
*/

Compilation message

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:30: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   71 |             int sz = (1 << j - 1);
      |                            ~~^~~

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Incorrect 1 ms 2392 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 279 ms 126768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 76 ms 9160 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 248 ms 105040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Incorrect 1 ms 2392 KB Output isn't correct
4 Halted 0 ms 0 KB -