oj.uz

Submission #1091498

# Submission time Handle Problem Language Result Execution time Memory
1091498 2024-09-21T02:13:51 Z thangdz2k7 Fish 3 (JOI24_fish3) C++17
100 / 100
 417 ms 54460 KB 
// author : thembululquaUwU
// 3.9.2024

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define endl '\n'

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

const int N = 3e5 + 5;
const int mod = 1e9 + 7;

void maxl(auto &a, auto b) {a = max(a, b);}
void minl(auto &a, auto b) {a = min(a, b);}

int n, q, lq[N], rq[N], sz[4 * N];
ll d, c[N], rs[N];
vector <int> query[N];

ll sum[4 * N], lz[4 * N];

void build(int s = 1, int l = 1, int r = n){
    sz[s] = r - l + 1, sum[s] = 0, lz[s] = 0;
    if (l == r) return; int mid = l + r >> 1;
    build(s << 1, l, mid); build(s << 1 | 1, mid + 1, r);
}

void add(int s, ll val){
    lz[s] += val; sum[s] += val * sz[s];
}

void down(int s){
    if (lz[s] == 0) return;
    add(s << 1, lz[s]); add(s << 1 | 1, lz[s]); lz[s] = 0;
}

void upd(int u, int v, ll val, int s = 1, int l = 1, int r = n){
    if (u <= l && r <= v){
        add(s, val);
        return;
    }

    int mid = l + r >> 1; down(s);
    if (mid >= u) upd(u, v, val, s << 1, l, mid);
    if (mid + 1 <= v) upd(u, v, val, s << 1 | 1, mid + 1, r);
    sum[s] = sum[s << 1] + sum[s << 1 | 1];
}

ll get(int u, int v, int s = 1, int l = 1, int r = n){
    if (u <= l && r <= v) return sum[s];
    int mid = l + r >> 1; down(s); ll ans = 0;
    if (mid >= u) ans += get(u, v, s << 1, l, mid);
    if (mid + 1 <= v) ans += get(u, v, s << 1 | 1, mid + 1, r);
    return ans;
}

ll up(ll a, ll b){return (a + b - 1) / b;}

struct DSU{
    vi par;

    DSU(int n){
        par.resize(n);
        for (int i = 0; i < n; ++ i) par[i] = i;
    }

    int find(int u){
        if (u == par[u]) return u;
        return par[u] = find(par[u]);
    }

    bool check(int u, int v){
        return find(u) == find(v);
    }

    void joint(int u, int v){
        u = find(u); v = find(v);
        par[u] = v;
    }
};

void solve(){
    cin >> n >> d;
    for (int i = 1; i <= n; ++ i) cin >> c[i];
    cin >> q;
    for (int i = 1; i <= q; ++ i) {
        cin >> lq[i] >> rq[i];
        query[rq[i]].pb(i);
    }

    DSU pqh(n + 1); build();
    for (int i = 1; i <= n; ++ i){
        int u = i;
        while (u > 1){
            int r = u - 1, l = pqh.find(r);
            ll nu = d * get(u, u), nr = d * get(r, r);
            ll cost = up((c[r] - nr) - (c[u] - nu), d);
            if (cost <= 0) break; pqh.joint(u, l); upd(l, r, cost); u = l;
        }
        for (int id : query[i]) {
            if (c[lq[id]] - d * get(lq[id], lq[id]) < 0) rs[id] = -1;
            else rs[id] = get(lq[id], rq[id]);
        }
    }
    for (int i = 1; i <= q; ++ i) cout << rs[i] << endl;
}

int main(){
    if (fopen("code.inp", "r")){
        freopen("code.inp", "r", stdin);
        freopen("code.out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int t = 1; // cin >> t;
    while (t --) solve();
    return 0;
}

Compilation message

Main.cpp:18:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   18 | void maxl(auto &a, auto b) {a = max(a, b);}
      |           ^~~~
Main.cpp:18:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   18 | void maxl(auto &a, auto b) {a = max(a, b);}
      |                    ^~~~
Main.cpp:19:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | void minl(auto &a, auto b) {a = min(a, b);}
      |           ^~~~
Main.cpp:19:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | void minl(auto &a, auto b) {a = min(a, b);}
      |                    ^~~~
Main.cpp: In function 'void build(int, int, int)':
Main.cpp:29:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   29 |     if (l == r) return; int mid = l + r >> 1;
      |     ^~
Main.cpp:29:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   29 |     if (l == r) return; int mid = l + r >> 1;
      |                         ^~~
Main.cpp:29:37: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |     if (l == r) return; int mid = l + r >> 1;
      |                                   ~~^~~
Main.cpp: In function 'void upd(int, int, ll, int, int, int)':
Main.cpp:48:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |     int mid = l + r >> 1; down(s);
      |               ~~^~~
Main.cpp: In function 'll get(int, int, int, int, int)':
Main.cpp:56:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |     int mid = l + r >> 1; down(s); ll ans = 0;
      |               ~~^~~
Main.cpp: In function 'void solve()':
Main.cpp:103:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  103 |             if (cost <= 0) break; pqh.joint(u, l); upd(l, r, cost); u = l;
      |             ^~
Main.cpp:103:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  103 |             if (cost <= 0) break; pqh.joint(u, l); upd(l, r, cost); u = l;
      |                                   ^~~
Main.cpp: In function 'int main()':
Main.cpp:115:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |         freopen("code.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:116:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |         freopen("code.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7516 KB Output is correct
2 Correct 3 ms 7516 KB Output is correct
3 Correct 3 ms 7516 KB Output is correct
4 Correct 6 ms 7772 KB Output is correct
5 Correct 5 ms 7768 KB Output is correct
6 Correct 5 ms 7772 KB Output is correct
7 Correct 4 ms 7708 KB Output is correct
8 Correct 5 ms 7852 KB Output is correct
9 Correct 5 ms 7732 KB Output is correct
10 Correct 5 ms 7772 KB Output is correct
11 Correct 5 ms 7772 KB Output is correct
12 Correct 5 ms 7856 KB Output is correct
13 Correct 5 ms 7772 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 43332 KB Output is correct
2 Correct 295 ms 43600 KB Output is correct
3 Correct 75 ms 15184 KB Output is correct
4 Correct 300 ms 42540 KB Output is correct
5 Correct 304 ms 46928 KB Output is correct
6 Correct 288 ms 48812 KB Output is correct
7 Correct 295 ms 48580 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 19044 KB Output is correct
2 Correct 407 ms 46968 KB Output is correct
3 Correct 399 ms 46932 KB Output is correct
4 Correct 415 ms 46872 KB Output is correct
5 Correct 403 ms 46944 KB Output is correct
6 Correct 364 ms 43600 KB Output is correct
7 Correct 390 ms 43532 KB Output is correct
8 Correct 393 ms 43600 KB Output is correct
9 Correct 373 ms 43600 KB Output is correct
10 Correct 294 ms 42100 KB Output is correct
11 Correct 290 ms 42068 KB Output is correct
12 Correct 346 ms 45392 KB Output is correct
13 Correct 361 ms 45216 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 32392 KB Output is correct
2 Correct 352 ms 43816 KB Output is correct
3 Correct 191 ms 22356 KB Output is correct
4 Correct 364 ms 43600 KB Output is correct
5 Correct 363 ms 45904 KB Output is correct
6 Correct 351 ms 54328 KB Output is correct
7 Correct 308 ms 41808 KB Output is correct
8 Correct 373 ms 54356 KB Output is correct
9 Correct 339 ms 47700 KB Output is correct
10 Correct 310 ms 47188 KB Output is correct
11 Correct 378 ms 51540 KB Output is correct
12 Correct 361 ms 50848 KB Output is correct
13 Correct 373 ms 54096 KB Output is correct
14 Correct 342 ms 50256 KB Output is correct
15 Correct 381 ms 54104 KB Output is correct
16 Correct 290 ms 50112 KB Output is correct

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7516 KB Output is correct
2 Correct 3 ms 7516 KB Output is correct
3 Correct 3 ms 7516 KB Output is correct
4 Correct 6 ms 7772 KB Output is correct
5 Correct 5 ms 7768 KB Output is correct
6 Correct 5 ms 7772 KB Output is correct
7 Correct 4 ms 7708 KB Output is correct
8 Correct 5 ms 7852 KB Output is correct
9 Correct 5 ms 7732 KB Output is correct
10 Correct 5 ms 7772 KB Output is correct
11 Correct 5 ms 7772 KB Output is correct
12 Correct 5 ms 7856 KB Output is correct
13 Correct 5 ms 7772 KB Output is correct
14 Correct 331 ms 43332 KB Output is correct
15 Correct 295 ms 43600 KB Output is correct
16 Correct 75 ms 15184 KB Output is correct
17 Correct 300 ms 42540 KB Output is correct
18 Correct 304 ms 46928 KB Output is correct
19 Correct 288 ms 48812 KB Output is correct
20 Correct 295 ms 48580 KB Output is correct
21 Correct 112 ms 19044 KB Output is correct
22 Correct 407 ms 46968 KB Output is correct
23 Correct 399 ms 46932 KB Output is correct
24 Correct 415 ms 46872 KB Output is correct
25 Correct 403 ms 46944 KB Output is correct
26 Correct 364 ms 43600 KB Output is correct
27 Correct 390 ms 43532 KB Output is correct
28 Correct 393 ms 43600 KB Output is correct
29 Correct 373 ms 43600 KB Output is correct
30 Correct 294 ms 42100 KB Output is correct
31 Correct 290 ms 42068 KB Output is correct
32 Correct 346 ms 45392 KB Output is correct
33 Correct 361 ms 45216 KB Output is correct
34 Correct 333 ms 32392 KB Output is correct
35 Correct 352 ms 43816 KB Output is correct
36 Correct 191 ms 22356 KB Output is correct
37 Correct 364 ms 43600 KB Output is correct
38 Correct 363 ms 45904 KB Output is correct
39 Correct 351 ms 54328 KB Output is correct
40 Correct 308 ms 41808 KB Output is correct
41 Correct 373 ms 54356 KB Output is correct
42 Correct 339 ms 47700 KB Output is correct
43 Correct 310 ms 47188 KB Output is correct
44 Correct 378 ms 51540 KB Output is correct
45 Correct 361 ms 50848 KB Output is correct
46 Correct 373 ms 54096 KB Output is correct
47 Correct 342 ms 50256 KB Output is correct
48 Correct 381 ms 54104 KB Output is correct
49 Correct 290 ms 50112 KB Output is correct
50 Correct 409 ms 54460 KB Output is correct
51 Correct 368 ms 48084 KB Output is correct
52 Correct 417 ms 51452 KB Output is correct
53 Correct 289 ms 49748 KB Output is correct
54 Correct 359 ms 53016 KB Output is correct
55 Correct 395 ms 54348 KB Output is correct
56 Correct 306 ms 50260 KB Output is correct
57 Correct 303 ms 46916 KB Output is correct
58 Correct 295 ms 46932 KB Output is correct
59 Correct 393 ms 52304 KB Output is correct
60 Correct 321 ms 50140 KB Output is correct
61 Correct 295 ms 49748 KB Output is correct
62 Correct 319 ms 49744 KB Output is correct
63 Correct 361 ms 52820 KB Output is correct
64 Correct 304 ms 50000 KB Output is correct