oj.uz

Submission #1011428

# Submission time Handle Problem Language Result Execution time Memory
1011428 2024-06-30T13:31:22 Z thinknoexit Fish 3 (JOI24_fish3) C++17
37 / 100
 551 ms 64424 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 300300;
int n;
ll a[N], b[N], p[N], ans[N];
ll qs[N];
ll tree[4 * N], lazy[4 * N];
ll mn[4 * N];
void build(int now = 1, int l = 1, int r = n) {
    if (l == r) {
        mn[now] = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(2 * now, l, mid), build(2 * now + 1, mid + 1, r);
    mn[now] = min(mn[2 * now], mn[2 * now + 1]);
}
ll qmn(int ql, int qr, int now = 1, int l = 1, int r = n) {
    if (l > qr || r < ql) return 1e18;
    if (ql <= l && r <= qr) return mn[now];
    int mid = (l + r) / 2;
    return min(qmn(ql, qr, 2 * now, l, mid), qmn(ql, qr, 2 * now + 1, mid + 1, r));
}
void lzy(int now, int l, int r) {
    if (lazy[now] == -1) return;
    tree[now] = lazy[now] * (r - l + 1);
    if (l != r) lazy[2 * now] = lazy[2 * now + 1] = lazy[now];
    lazy[now] = -1;
}
void update(int ql, int qr, ll w, int now = 1, int l = 1, int r = n) {
    lzy(now, l, r);
    if (l > qr || r < ql) return;
    if (ql <= l && r <= qr) {
        lazy[now] = w;
        lzy(now, l, r);
        return;
    }
    int mid = (l + r) / 2;
    update(ql, qr, w, 2 * now, l, mid), update(ql, qr, w, 2 * now + 1, mid + 1, r);
    tree[now] = tree[2 * now] + tree[2 * now + 1];
}
ll query(int ql, int qr, int now = 1, int l = 1, int r = n) {
    lzy(now, l, r);
    if (l > qr || r < ql) return 0ll;
    if (ql <= l && r <= qr) return tree[now];
    int mid = (l + r) / 2;
    return query(ql, qr, 2 * now, l, mid) + query(ql, qr, 2 * now + 1, mid + 1, r);
}
vector<pair<int, int>> Q[N];
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    memset(lazy, -1, sizeof lazy);
    ll d;
    cin >> n >> d;
    for (int i = 1;i <= n;i++) {
        // c[i] = d * a[i] + b[i]
        ll c;
        cin >> c;
        a[i] = c / d;
        b[i] = c % d;
    }
    for (int i = 2;i <= n;i++) {
        p[i] = p[i - 1];
        if (b[i - 1] > b[i]) p[i]++;
    }
    for (int i = 1;i <= n;i++) {
        a[i] -= p[i];
        qs[i] = qs[i - 1] + a[i];
    }
    build();
    int q;
    cin >> q;
    for (int i = 1;i <= q;i++) {
        int l, r;
        cin >> l >> r;
        Q[r].push_back({ l, i });
    }
    // do like subtask 3
    int pre = 1;
    stack<pair<ll, int>> st;
    for (int i = 1;i <= n;i++) {
        while (!st.empty() && st.top().first >= a[i]) {
            st.pop();
        }
        if (st.empty()) update(1, i, a[i]);
        else update(st.top().second + 1, i, a[i]);
        st.push({ a[i], i });
        for (auto& x : Q[i]) {
            if (qmn(x.first, i) + p[x.first] < 0) {
                ans[x.second] = -1;
                continue;
            }
            ans[x.second] = qs[i] - qs[x.first - 1] - query(x.first, i);
        }
    }
    for (int i = 1;i <= q;i++) {
        cout << ans[i] << '\n';
    }
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:80:9: warning: unused variable 'pre' [-Wunused-variable]
   80 |     int pre = 1;
      |         ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16728 KB Output is correct
2 Correct 7 ms 16732 KB Output is correct
3 Correct 7 ms 16732 KB Output is correct
4 Correct 9 ms 17440 KB Output is correct
5 Correct 8 ms 17244 KB Output is correct
6 Correct 10 ms 17272 KB Output is correct
7 Correct 8 ms 16988 KB Output is correct
8 Correct 8 ms 17240 KB Output is correct
9 Correct 9 ms 17244 KB Output is correct
10 Correct 10 ms 17124 KB Output is correct
11 Correct 9 ms 17244 KB Output is correct
12 Correct 9 ms 17244 KB Output is correct
13 Correct 10 ms 17244 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 57172 KB Output is correct
2 Correct 406 ms 56580 KB Output is correct
3 Correct 92 ms 26856 KB Output is correct
4 Correct 263 ms 56400 KB Output is correct
5 Correct 265 ms 56148 KB Output is correct
6 Incorrect 321 ms 54352 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 30684 KB Output is correct
2 Correct 435 ms 63828 KB Output is correct
3 Correct 421 ms 63824 KB Output is correct
4 Correct 443 ms 63848 KB Output is correct
5 Correct 383 ms 63852 KB Output is correct
6 Correct 404 ms 57396 KB Output is correct
7 Correct 405 ms 57428 KB Output is correct
8 Correct 398 ms 60712 KB Output is correct
9 Correct 458 ms 60768 KB Output is correct
10 Correct 473 ms 64068 KB Output is correct
11 Correct 459 ms 64252 KB Output is correct
12 Correct 421 ms 64336 KB Output is correct
13 Correct 551 ms 64424 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 414 ms 46928 KB Output is correct
2 Correct 409 ms 57168 KB Output is correct
3 Correct 241 ms 35504 KB Output is correct
4 Correct 382 ms 60500 KB Output is correct
5 Correct 410 ms 61812 KB Output is correct
6 Correct 406 ms 63724 KB Output is correct
7 Correct 377 ms 52304 KB Output is correct
8 Correct 436 ms 63636 KB Output is correct
9 Incorrect 336 ms 56484 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16728 KB Output is correct
2 Correct 7 ms 16732 KB Output is correct
3 Correct 7 ms 16732 KB Output is correct
4 Correct 9 ms 17440 KB Output is correct
5 Correct 8 ms 17244 KB Output is correct
6 Correct 10 ms 17272 KB Output is correct
7 Correct 8 ms 16988 KB Output is correct
8 Correct 8 ms 17240 KB Output is correct
9 Correct 9 ms 17244 KB Output is correct
10 Correct 10 ms 17124 KB Output is correct
11 Correct 9 ms 17244 KB Output is correct
12 Correct 9 ms 17244 KB Output is correct
13 Correct 10 ms 17244 KB Output is correct
14 Correct 406 ms 57172 KB Output is correct
15 Correct 406 ms 56580 KB Output is correct
16 Correct 92 ms 26856 KB Output is correct
17 Correct 263 ms 56400 KB Output is correct
18 Correct 265 ms 56148 KB Output is correct
19 Incorrect 321 ms 54352 KB Output isn't correct
20 Halted 0 ms 0 KB -