oj.uz

Submission #991053

# Submission time Handle Problem Language Result Execution time Memory
991053 2024-06-01T07:21:23 Z grt Fish 3 (JOI24_fish3) C++17
27 / 100
 300 ms 66128 KB 
#include <bits/stdc++.h>
#define ST first
#define ND second
#define PB push_back

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;

const int nax = 300 * 1000 + 10;

struct SegTree {
    ll T[(1 << 20)];
    int R;
    void upd(int a, ll x) {
        a += R;
        T[a] += x;
        while (a > 1) {
            a >>= 1;
            T[a] += x;
        }
    }
    ll qr(int a, int b) {
        a += R; b += R;
        if (a > b) return 0LL;
        ll w = T[a] + (a != b ? T[b] : 0LL);
        while (a/2 != b/2) {
            if (a % 2 == 0) w += T[a + 1];
            if (b % 2 == 1) w += T[b - 1];
            a >>= 1;
            b >>= 1;
         }
        return w;
    }
    void init(int n) {
        R = 1;
        while (R < n) R <<= 1;
        for (int i = 0; i < 2 * R; ++i) T[i] = 0;
    }
    int go_down() {
        int v = 1;
        while (v < R) {
            if (T[2 * v + 1] != 0) v = v*2 + 1;
            else v = v*2;
        }
        return v - R;
    }
};

vector<pair<int,int>>qrs[nax];
ll ans[nax];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    ll d;
    cin >> n >> d;
    vector<ll> a(n);
    for (ll &x : a) cin >> x;
    cin >> q;
    vector<ll> demands(n);

    for (int i = 1; i < n; ++i) {
        demands[i] = a[i] - a[i - 1];
        if (demands[i] < 0) {
            demands[i] = (abs(demands[i]) - 1) / d + 1;
        } else {
            demands[i] = -(demands[i] / d);
        }
    }

    for (int l,r, i = 0; i < q; ++i) {
        cin >> l >> r;
        l--, r--;
        qrs[r].emplace_back(l, i);
    }
    
    SegTree s, lft, closed, total;
    s.init(n);
    lft.init(n);
    closed.init(n);
    total.init(n);
    for (int i = 1; i < n; ++i) {
        // update value i
        //cerr << "i: " << i << " " << demands[i] << "\n";
        if (demands[i] < 0) {
            s.upd(i, -demands[i]); // I can give that many
        } else {
            lft.upd(i, demands[i] * i);
            total.upd(i, demands[i]);
            while (demands[i] > 0) {
                if (s.T[1] == 0) break;
                int v = s.go_down();
                ll me = min(demands[i], s.qr(v,v));
                s.upd(v, -me);
                closed.upd(v, me);
                lft.upd(v, -me * v);
                //cerr << "segment: " << v << "->" << i << " " << me << " times\n";
            }
        }
        for (auto [l, id] : qrs[i]) {
            ll open = total.qr(l + 1, i) - closed.qr(l + 1, i);
            ll res = lft.qr(l + 1, i);
            ll me = a[l] / d;
            //cerr << "(" << total.qr(l+1,i) << " " << closed.qr(l+1, i) << ")"  << " " << res << " " << me << "\n";
            if (me < open) {
                ans[id] = -1;
            } else {
                ans[id] = res - (ll)l * open;
            }
        }
    }

    for (int i = 0; i < q; ++i) cout << ans[i] << "\n";
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 40280 KB Output is correct
2 Correct 15 ms 40284 KB Output is correct
3 Incorrect 15 ms 40284 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 55088 KB Output is correct
2 Correct 241 ms 58812 KB Output is correct
3 Correct 111 ms 50068 KB Output is correct
4 Correct 243 ms 58452 KB Output is correct
5 Correct 263 ms 58672 KB Output is correct
6 Correct 247 ms 58452 KB Output is correct
7 Correct 228 ms 58328 KB Output is correct

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 121 ms 51432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 53968 KB Output is correct
2 Correct 246 ms 59472 KB Output is correct
3 Correct 184 ms 54100 KB Output is correct
4 Correct 268 ms 62864 KB Output is correct
5 Correct 263 ms 64852 KB Output is correct
6 Correct 255 ms 65944 KB Output is correct
7 Correct 258 ms 63820 KB Output is correct
8 Correct 269 ms 66128 KB Output is correct
9 Correct 258 ms 58704 KB Output is correct
10 Correct 230 ms 58532 KB Output is correct
11 Correct 263 ms 62856 KB Output is correct
12 Correct 253 ms 62180 KB Output is correct
13 Correct 300 ms 65876 KB Output is correct
14 Correct 248 ms 61864 KB Output is correct
15 Correct 260 ms 65872 KB Output is correct
16 Correct 254 ms 61788 KB Output is correct

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 40280 KB Output is correct
2 Correct 15 ms 40284 KB Output is correct
3 Incorrect 15 ms 40284 KB Output isn't correct
4 Halted 0 ms 0 KB -