oj.uz

Submission #985599

# Submission time Handle Problem Language Result Execution time Memory
985599 2024-05-18T09:34:06 Z Whisper Fish 3 (JOI24_fish3) C++17
100 / 100
 466 ms 60496 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define int long long
#define For(i, a, b) for (int i = (a); i <= (b); i++)
#define Ford(i, a, b) for (int i = (b); i >= (a); i --)
#define Rep(i, n) for (int i = 0; i < (n); ++i)
#define Repd(i, n) for (int i = (n) - 1; i >= 0; --i)

#define overload(_1, _2, _3, NAME, ...) NAME
#define FOR(...) overload(__VA_ARGS__, For, Rep)(__VA_ARGS__)
#define FORD(...) overload(__VA_ARGS__, Ford, Repd)(__VA_ARGS__)

#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)


constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void setupIO(){
    #define name "Whisper"
    //Phu Trong from Nguyen Tat Thanh High School for gifted student
    srand(time(NULL));
    cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr);
    //freopen(name".inp", "r", stdin);
    //freopen(name".out", "w", stdout);
    cout << fixed << setprecision(10);
}

template <class X, class Y>
    bool minimize(X &x, const Y &y){
        X eps = 1e-9;
        if (x > y + eps) {x = y; return 1;}
        return 0;
    }

template <class X, class Y>
    bool maximize(X &x, const Y &y){
        X eps = 1e-9;
        if (x + eps < y) {x = y; return 1;}
        return 0;
    }
#define MAX     300005
int numFish, numQuery, d;
int expect[MAX];
vector<pair<int, int>> event[MAX];
struct Node{
    int mx, sum;
    Node(){
        mx = -1, sum = 0;
    }
    Node(int _mx, int _sum): mx(_mx), sum(_sum){}
    friend Node operator + (const Node& a, const Node& b){
        Node res;
        res.mx = max(a.mx, b.mx);
        res.sum = a.sum + b.sum;
        return res;
    }
};

struct SegmentTree{
    int n;
    vector<Node> st;
    vector<int> lz;
    SegmentTree(){}
    SegmentTree(int _n = 0){
        this -> n = _n;
        st.resize((n << 2));
        lz.resize((n << 2), -1);
    }
    void pushDown(int id, int l, int r){
        if (lz[id] == -1) return;
        int m = (l + r) >> 1;
        st[id << 1].sum = (m - l + 1) * lz[id];
        st[id << 1].mx = lz[id];
        st[id << 1 | 1].sum = (r - m) * lz[id];
        st[id << 1 | 1].mx = lz[id];
        lz[id << 1] = lz[id];
        lz[id << 1 | 1] = lz[id];
        lz[id] = -1;
    }
    void Modify(int id, int l, int r, int u, int v, int val){
        if (u > r || v < l) return;
        if (u <= l && v >= r) {
            st[id].sum = (r - l + 1) * val;
            st[id].mx = val;
            lz[id] = val;
            return;
        }
        int m = (l + r) >> 1;
        pushDown(id, l, r);
        Modify(id << 1, l, m, u, v, val);
        Modify(id << 1 | 1, m + 1, r, u, v, val);
        st[id] = st[id << 1] + st[id << 1 | 1];
    }
    int Query(int id, int l, int r, int u, int v){
        if (u > r || v < l) return 0;
        if (u <= l && v >= r) return st[id].sum;
        int m = (l + r) >> 1;
        pushDown(id, l, r);
        int ql = Query(id << 1, l, m, u, v);
        int qr = Query(id << 1 | 1, m + 1, r, u, v);
        return (ql + qr);
    }
    int find(int id, int l, int r, int u, int v, int x){
        if (u > r || v < l) return -1;
        if (l == r && st[id].mx > x) return l;
        else if (l == r) return -1;
        int m = (l + r) >> 1;
        pushDown(id, l, r);
        int ans = -1;
        if (st[id << 1].mx > x) ans = find(id << 1, l, m, u, v, x);
        if (ans == -1) ans = find(id << 1 | 1, m + 1, r, u, v, x);
        return ans;
    }
};

int need[MAX], dis[MAX], A[MAX];

int ans[MAX];
void Whisper(){
    cin >> numFish >> d;
    for (int i = 1; i <= numFish; ++i) cin >> expect[i], need[i] = expect[i];
    for (int i = numFish - 1; i >= 1; --i){
        if (need[i] > need[i + 1]){
            int diff = need[i] - need[i + 1];
            diff = (diff + d - 1) / d;
            A[i] += diff;
            need[i] -= d * diff;
            dis[i] = diff;
        }
    }

    for (int i = 1; i <= numFish; ++i) A[i] += A[i - 1];
    SegmentTree st(numFish + 1);

    cin >> numQuery;
    for (int i = 1; i <= numQuery; ++i){
        int l, r; cin >> l >> r;
        event[r].emplace_back(l, i);
    }

    for (int r = 1; r <= numFish; ++r){
        if (r > 1){
            int id = st.find(1, 1, numFish, 1, r - 1, dis[r]);
            if (id == -1) id = r;
            if (id <= r)
                st.Modify(1, 1, numFish, id, r, dis[r]);
        }
        else{
            st.Modify(1, 1, numFish, 1, 1, dis[1]);
        }
        for (pair<int, int>&x : event[r]){
            int l = x.first, id = x.second;
            int num = st.Query(1, 1, numFish, l, l);
            if(need[l] + d * num < 0) ans[id] = -1;
            else{
                ans[id] = A[r] - A[l - 1] - st.Query(1, 1, numFish, l, r);
            }
        }
    }
    for (int i = 1; i <= numQuery; ++i) cout << ans[i] << "\n";
}


signed main(){
    setupIO();
    int Test = 1;
//    cin >> Test;
    for ( int i = 1 ; i <= Test ; i++ ){
        Whisper();
        if (i < Test) cout << '\n';
    }
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 5 ms 15196 KB Output is correct
5 Correct 5 ms 15196 KB Output is correct
6 Correct 5 ms 14936 KB Output is correct
7 Correct 4 ms 14940 KB Output is correct
8 Correct 5 ms 15196 KB Output is correct
9 Correct 4 ms 15192 KB Output is correct
10 Correct 5 ms 15192 KB Output is correct
11 Correct 4 ms 15196 KB Output is correct
12 Correct 4 ms 11100 KB Output is correct
13 Correct 4 ms 10940 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 57072 KB Output is correct
2 Correct 345 ms 56440 KB Output is correct
3 Correct 78 ms 26020 KB Output is correct
4 Correct 287 ms 56144 KB Output is correct
5 Correct 279 ms 56044 KB Output is correct
6 Correct 297 ms 55964 KB Output is correct
7 Correct 329 ms 55960 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 29784 KB Output is correct
2 Correct 396 ms 60392 KB Output is correct
3 Correct 394 ms 60396 KB Output is correct
4 Correct 371 ms 60496 KB Output is correct
5 Correct 383 ms 60496 KB Output is correct
6 Correct 351 ms 57336 KB Output is correct
7 Correct 353 ms 57360 KB Output is correct
8 Correct 370 ms 57320 KB Output is correct
9 Correct 369 ms 57324 KB Output is correct
10 Correct 348 ms 55796 KB Output is correct
11 Correct 345 ms 55892 KB Output is correct
12 Correct 369 ms 58840 KB Output is correct
13 Correct 369 ms 58964 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 51992 KB Output is correct
2 Correct 376 ms 56916 KB Output is correct
3 Correct 190 ms 34472 KB Output is correct
4 Correct 359 ms 56916 KB Output is correct
5 Correct 407 ms 56828 KB Output is correct
6 Correct 460 ms 60400 KB Output is correct
7 Correct 364 ms 54100 KB Output is correct
8 Correct 441 ms 60488 KB Output is correct
9 Correct 294 ms 56284 KB Output is correct
10 Correct 275 ms 56100 KB Output is correct
11 Correct 360 ms 56916 KB Output is correct
12 Correct 344 ms 56400 KB Output is correct
13 Correct 445 ms 60148 KB Output is correct
14 Correct 345 ms 56032 KB Output is correct
15 Correct 466 ms 60244 KB Output is correct
16 Correct 345 ms 56148 KB Output is correct

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 5 ms 15196 KB Output is correct
5 Correct 5 ms 15196 KB Output is correct
6 Correct 5 ms 14936 KB Output is correct
7 Correct 4 ms 14940 KB Output is correct
8 Correct 5 ms 15196 KB Output is correct
9 Correct 4 ms 15192 KB Output is correct
10 Correct 5 ms 15192 KB Output is correct
11 Correct 4 ms 15196 KB Output is correct
12 Correct 4 ms 11100 KB Output is correct
13 Correct 4 ms 10940 KB Output is correct
14 Correct 352 ms 57072 KB Output is correct
15 Correct 345 ms 56440 KB Output is correct
16 Correct 78 ms 26020 KB Output is correct
17 Correct 287 ms 56144 KB Output is correct
18 Correct 279 ms 56044 KB Output is correct
19 Correct 297 ms 55964 KB Output is correct
20 Correct 329 ms 55960 KB Output is correct
21 Correct 114 ms 29784 KB Output is correct
22 Correct 396 ms 60392 KB Output is correct
23 Correct 394 ms 60396 KB Output is correct
24 Correct 371 ms 60496 KB Output is correct
25 Correct 383 ms 60496 KB Output is correct
26 Correct 351 ms 57336 KB Output is correct
27 Correct 353 ms 57360 KB Output is correct
28 Correct 370 ms 57320 KB Output is correct
29 Correct 369 ms 57324 KB Output is correct
30 Correct 348 ms 55796 KB Output is correct
31 Correct 345 ms 55892 KB Output is correct
32 Correct 369 ms 58840 KB Output is correct
33 Correct 369 ms 58964 KB Output is correct
34 Correct 320 ms 51992 KB Output is correct
35 Correct 376 ms 56916 KB Output is correct
36 Correct 190 ms 34472 KB Output is correct
37 Correct 359 ms 56916 KB Output is correct
38 Correct 407 ms 56828 KB Output is correct
39 Correct 460 ms 60400 KB Output is correct
40 Correct 364 ms 54100 KB Output is correct
41 Correct 441 ms 60488 KB Output is correct
42 Correct 294 ms 56284 KB Output is correct
43 Correct 275 ms 56100 KB Output is correct
44 Correct 360 ms 56916 KB Output is correct
45 Correct 344 ms 56400 KB Output is correct
46 Correct 445 ms 60148 KB Output is correct
47 Correct 345 ms 56032 KB Output is correct
48 Correct 466 ms 60244 KB Output is correct
49 Correct 345 ms 56148 KB Output is correct
50 Correct 383 ms 60496 KB Output is correct
51 Correct 365 ms 57424 KB Output is correct
52 Correct 359 ms 57168 KB Output is correct
53 Correct 349 ms 55892 KB Output is correct
54 Correct 361 ms 58964 KB Output is correct
55 Correct 445 ms 60240 KB Output is correct
56 Correct 325 ms 56052 KB Output is correct
57 Correct 298 ms 56148 KB Output is correct
58 Correct 331 ms 56224 KB Output is correct
59 Correct 388 ms 58192 KB Output is correct
60 Correct 330 ms 56044 KB Output is correct
61 Correct 350 ms 55772 KB Output is correct
62 Correct 348 ms 55892 KB Output is correct
63 Correct 359 ms 58704 KB Output is correct
64 Correct 341 ms 56404 KB Output is correct