oj.uz

Submission #994909

# Submission time Handle Problem Language Result Execution time Memory
994909 2024-06-08T08:25:03 Z prvocislo Fish 3 (JOI24_fish3) C++17
100 / 100
 515 ms 65212 KB 
// He was a moth to the flame
// She was holding the matches
// Soon, she's gonna find stealing other people's toys
// On the playground won't make you many friends

#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
typedef long double ld;
using namespace std;

struct sgttree // range add, range sum
{
    vector<ll> st, lz; 
    vector<int> l, r;
    void init(int n)
    {
        int n2 = 1;
        while (n2 <= n) n2 <<= 1;
        st.assign(n2 * 2, 0), lz.assign(n2 * 2, 0), l.assign(n2 * 2, 0), r.assign(n2 * 2, 0);
        for (int i = n2; i < n2 * 2; i++) l[i] = r[i] = i - n2;
        for (int i = n2 - 1; i > 0; i--) l[i] = l[i * 2], r[i] = r[i * 2 + 1];
    }
    void upd(int vr, ll x)
    {
        st[vr] += ((ll)(r[vr] - l[vr] + 1)) * x, lz[vr] += x;
    }
    void unlazy(int vr)
    {
        upd(vr * 2, lz[vr]), upd(vr * 2 + 1, lz[vr]);
        lz[vr] = 0;
    }
    void update(int li, int ri, ll x, int vr = 1)
    {
        if (ri < l[vr] || r[vr] < li) return;
        if (li <= l[vr] && r[vr] <= ri) 
            return upd(vr, x), void();
        unlazy(vr);
        update(li, ri, x, vr * 2), update(li, ri, x, vr * 2 + 1);
        st[vr] = st[vr * 2] + st[vr * 2 + 1];
    }
    ll query(int li, int ri, int vr = 1)
    {
        if (ri < l[vr] || r[vr] < li) return 0;
        if (li <= l[vr] && r[vr] <= ri) return st[vr];
        unlazy(vr);
        return query(li, ri, vr * 2) + query(li, ri, vr * 2 + 1);
    }
};
struct block // lx az rx, na poziciach li az ri
{
    int li, ri;
    ll lx, rx;
};
struct query
{
    int l, r, i;
};
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, q; ll d;
    cin >> n >> d;
    vector<ll> c(n);
    for (int i = 0; i < n; i++) cin >> c[i];
    cin >> q;
    vector<ll> ans(q);
    vector<vector<query> > qu(n);
    for (int i = 0; i < q; i++)
    {
        query qi;
        cin >> qi.l >> qi.r, qi.l--, qi.r--, qi.i = i;
        qu[qi.r].push_back(qi);
    }
    sgttree st; st.init(n);
    vector<block> s;
    for (int i = 0; i < n; i++)
    {
        block nw;
        nw.li = nw.ri = i, nw.lx = nw.rx = c[i];
        while (s.size() && s.back().rx > nw.lx)
        {
            block b = s.back();
            ll sub = (b.rx - nw.lx + d - 1) / d;
            s.pop_back();
            st.update(b.li, b.ri, sub);
            nw.li = b.li, nw.lx = b.lx - sub * d;
        }
        s.push_back(nw);
        for (query qi : qu[i])
        {
            ll lf = c[qi.l] - st.query(qi.l, qi.l) * d;
            if (lf < 0) ans[qi.i] = -1;
            else ans[qi.i] = st.query(qi.l, qi.r);
        }
    }
    for (int i = 0; i < q; i++) cout << ans[i] << "\n";
    return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 3 ms 860 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 2 ms 684 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 3 ms 860 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 3 ms 980 KB Output is correct
13 Correct 3 ms 860 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 419 ms 55128 KB Output is correct
2 Correct 364 ms 55232 KB Output is correct
3 Correct 86 ms 12368 KB Output is correct
4 Correct 300 ms 48664 KB Output is correct
5 Correct 296 ms 48580 KB Output is correct
6 Correct 315 ms 53948 KB Output is correct
7 Correct 311 ms 55900 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 16312 KB Output is correct
2 Correct 428 ms 56172 KB Output is correct
3 Correct 490 ms 56180 KB Output is correct
4 Correct 407 ms 56296 KB Output is correct
5 Correct 428 ms 56284 KB Output is correct
6 Correct 394 ms 50636 KB Output is correct
7 Correct 392 ms 50596 KB Output is correct
8 Correct 437 ms 53852 KB Output is correct
9 Correct 422 ms 53704 KB Output is correct
10 Correct 353 ms 64692 KB Output is correct
11 Correct 337 ms 65212 KB Output is correct
12 Correct 385 ms 57692 KB Output is correct
13 Correct 387 ms 57544 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 402 ms 36028 KB Output is correct
2 Correct 409 ms 50300 KB Output is correct
3 Correct 274 ms 23060 KB Output is correct
4 Correct 432 ms 53548 KB Output is correct
5 Correct 465 ms 54612 KB Output is correct
6 Correct 515 ms 56160 KB Output is correct
7 Correct 379 ms 40528 KB Output is correct
8 Correct 445 ms 56288 KB Output is correct
9 Correct 332 ms 49612 KB Output is correct
10 Correct 308 ms 49288 KB Output is correct
11 Correct 379 ms 53468 KB Output is correct
12 Correct 342 ms 52736 KB Output is correct
13 Correct 401 ms 55832 KB Output is correct
14 Correct 300 ms 51708 KB Output is correct
15 Correct 401 ms 55896 KB Output is correct
16 Correct 314 ms 51816 KB Output is correct

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 3 ms 860 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 2 ms 684 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 3 ms 860 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 3 ms 980 KB Output is correct
13 Correct 3 ms 860 KB Output is correct
14 Correct 419 ms 55128 KB Output is correct
15 Correct 364 ms 55232 KB Output is correct
16 Correct 86 ms 12368 KB Output is correct
17 Correct 300 ms 48664 KB Output is correct
18 Correct 296 ms 48580 KB Output is correct
19 Correct 315 ms 53948 KB Output is correct
20 Correct 311 ms 55900 KB Output is correct
21 Correct 139 ms 16312 KB Output is correct
22 Correct 428 ms 56172 KB Output is correct
23 Correct 490 ms 56180 KB Output is correct
24 Correct 407 ms 56296 KB Output is correct
25 Correct 428 ms 56284 KB Output is correct
26 Correct 394 ms 50636 KB Output is correct
27 Correct 392 ms 50596 KB Output is correct
28 Correct 437 ms 53852 KB Output is correct
29 Correct 422 ms 53704 KB Output is correct
30 Correct 353 ms 64692 KB Output is correct
31 Correct 337 ms 65212 KB Output is correct
32 Correct 385 ms 57692 KB Output is correct
33 Correct 387 ms 57544 KB Output is correct
34 Correct 402 ms 36028 KB Output is correct
35 Correct 409 ms 50300 KB Output is correct
36 Correct 274 ms 23060 KB Output is correct
37 Correct 432 ms 53548 KB Output is correct
38 Correct 465 ms 54612 KB Output is correct
39 Correct 515 ms 56160 KB Output is correct
40 Correct 379 ms 40528 KB Output is correct
41 Correct 445 ms 56288 KB Output is correct
42 Correct 332 ms 49612 KB Output is correct
43 Correct 308 ms 49288 KB Output is correct
44 Correct 379 ms 53468 KB Output is correct
45 Correct 342 ms 52736 KB Output is correct
46 Correct 401 ms 55832 KB Output is correct
47 Correct 300 ms 51708 KB Output is correct
48 Correct 401 ms 55896 KB Output is correct
49 Correct 314 ms 51816 KB Output is correct
50 Correct 437 ms 56152 KB Output is correct
51 Correct 416 ms 50504 KB Output is correct
52 Correct 390 ms 53860 KB Output is correct
53 Correct 356 ms 64828 KB Output is correct
54 Correct 386 ms 57768 KB Output is correct
55 Correct 421 ms 56148 KB Output is correct
56 Correct 296 ms 51940 KB Output is correct
57 Correct 274 ms 48568 KB Output is correct
58 Correct 299 ms 48624 KB Output is correct
59 Correct 391 ms 53988 KB Output is correct
60 Correct 307 ms 51828 KB Output is correct
61 Correct 385 ms 64956 KB Output is correct
62 Correct 340 ms 64192 KB Output is correct
63 Correct 391 ms 57420 KB Output is correct
64 Correct 267 ms 51796 KB Output is correct