oj.uz

Submission #958888

# Submission time Handle Problem Language Result Execution time Memory
958888 2024-04-07T02:45:51 Z gaga999 Fish 2 (JOI22_fish2) C++17
100 / 100
 1413 ms 79356 KB 
// #pragma GCC optimize("Ofast,no-stack-protector")
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx,avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define lowbit(x) ((x) & -(x))
#define ml(a, b) ((1ll * (a) * (b)) % M)
#define tml(a, b) (a) = ((1ll * (a) * (b)) % M)
#define ad(a, b) ((0ll + (a) + (b)) % M)
#define tad(a, b) (a) = ((0ll + (a) + (b)) % M)
#define mi(a, b) ((0ll + M + (a) - (b)) % M)
#define tmi(a, b) (a) = ((0ll + M + (a) - (b)) % M)
#define tmin(a, b) (a) = min((a), (b))
#define tmax(a, b) (a) = max((a), (b))
#define iter(a) (a).begin(), (a).end()
#define riter(a) (a).rbegin(), (a).rend()
#define init(a, b) memset((a), (b), sizeof(a))
#define cpy(a, b) memcpy((a), (b), sizeof(a))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define size(x) (int)x.size()
#define pb emplace_back
#define mpr make_pair
#define ls(i) ((i) << 1)
#define rs(i) ((i) << 1 | 1)
#define INF 0x3f3f3f3f
#define NIF 0xc0c0c0c0
#define eps 1e-9
#define F first
#define S second
#define AC cin.tie(0)->sync_with_stdio(0)
using namespace std;
typedef long long llt;
typedef __int128_t lll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<llt, llt> pll;
typedef complex<double> cd;
// const int M = 998244353;

// random_device rm;
// mt19937 rg(rm());
// default_random_engine rg(rm());
// uniform_int_distribution<int> rd(INT_MIN, INT_MAX);
// uniform_real_distribution<double> rd(0, M_PI);

void db() { cerr << "\n"; }
template <class T, class... U>
void db(T a, U... b) { cerr << a << " ", db(b...); }

inline char gc()
{
    const static int SZ = 1 << 16;
    static char buf[SZ], *p1, *p2;
    if (p1 == p2 && (p2 = buf + fread(p1 = buf, 1, SZ, stdin), p1 == p2))
        return -1;
    return *p1++;
}
void rd() {}
template <typename T, typename... U>
void rd(T &x, U &...y)
{
    x = 0;
    bool f = 0;
    char c = gc();
    while (!isdigit(c))
        f ^= !(c ^ 45), c = gc();
    while (isdigit(c))
        x = (x << 1) + (x << 3) + (c ^ 48), c = gc();
    f && (x = -x), rd(y...);
}

template <typename T>
void prt(T x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        prt(x / 10);
    putchar((x % 10) ^ 48);
}
const llt MX = 1ll << 60;
const int N = 1e5 + 5;

struct P
{
    llt sum;
    int ans;
    vector<llt> lsm, rsm, lnd, rnd;
    vector<int> lnb, rnb;
    inline void ini(int v)
    {
        sum = v, ans = 1;
        lsm = rsm = vector<llt>(1, 0);
        lnd = rnd = vector<llt>(1, v);
        lnb = rnb = vector<int>(1, 0);
    }
} tr[N << 1];

P operator+(P &l, P &r)
{
    P p;
    int slr = size(l.rnd), srl = size(r.lnd);
    p.sum = l.sum + r.sum, p.ans = 0;
    p.lsm = l.lsm, p.rsm = r.rsm;
    p.lnd = l.lnd, p.rnd = r.rnd;
    p.lnb = l.lnb, p.rnb = r.rnb;
    for (int i = 0; i < srl; i++)
        if (r.lnd[i] > l.sum)
            p.lnd.pb(r.lnd[i] - l.sum), p.lsm.pb(r.lsm[i] + l.sum);
    p.lnb.resize(size(p.lnd), 0);
    if (size(p.lnd) > size(l.lnd))
        p.lnb[size(l.lnd)] = l.ans;
    else
        p.ans += l.ans;
    for (int i = 0; i < slr; i++)
        if (l.rnd[i] > r.sum)
            p.rnd.pb(l.rnd[i] - r.sum), p.rsm.pb(l.rsm[i] + r.sum);
    p.rnb.resize(size(p.rnd), 0);
    if (size(p.rnd) > size(r.rnd))
        p.rnb[size(r.rnd)] = r.ans;
    else
        p.ans += r.ans;
    l.rnb.pb(0), l.rnd.pb(MX), l.rsm.pb(l.sum);
    r.lnb.pb(0), r.lnd.pb(MX), r.lsm.pb(r.sum);
    auto move = [&](int p1, int p2, int num) -> void
    {
        bool ok = 1;
        while (ok)
        {
            ok = 0;
            while (l.rnd[p1] <= r.lsm[p2])
                p1++, ok = 1;
            while (r.lnd[p2] <= l.rsm[p1])
                p2++, ok = 1;
        }
        if (p1 == slr && p2 == srl)
            p.ans += num;
        else if (p1 == slr)
        {
            int i = 0;
            while (p.lsm[i] < l.sum + r.lsm[p2])
                i++;
            p.lnb[i] += num;
        }
        else if (p2 == srl)
        {
            int i = 0;
            while (p.rsm[i] < r.sum + l.rsm[p1])
                i++;
            p.rnb[i] += num;
        }
    };
    for (int i = 0; i < slr; i++)
        if (l.rnb[i])
            move(i, 0, l.rnb[i]);
    for (int i = 0; i < srl; i++)
        if (r.lnb[i])
            move(0, i, r.lnb[i]);
    l.rnb.pop_back(), l.rnd.pop_back(), l.rsm.pop_back();
    r.lnb.pop_back(), r.lnd.pop_back(), r.lsm.pop_back();
    return p;
}

signed main()
{
    int n, q, x, a, b;
    rd(n);
    auto pul = [&](int i) -> void
    {
        tr[i] = tr[ls(i)] + tr[rs(i)];
    };
    auto cg = [&](int p, int v) -> void
    {
        p += n - 1, tr[p].ini(v);
        for (p >>= 1; p; p >>= 1)
            pul(p);
    };
    auto qy = [&](int l, int r) -> int
    {
        l += n - 1, r += n - 1;
        if (l == r)
            return tr[l].ans;
        P p1 = tr[l++], p2 = tr[r--];
        for (; l <= r; l >>= 1, r >>= 1)
        {
            if (l & 1)
                p1 = p1 + tr[l++];
            if (~r & 1)
                p2 = tr[r--] + p2;
        }
        return (p1 + p2).ans;
    };
    for (int i = 0; i < n; i++)
        rd(x), tr[i + n].ini(x);
    for (int i = n - 1; i > 0; i--)
        pul(i);
    rd(q);
    while (q--)
    {
        rd(x, a, b);
        if (x == 1)
            cg(a, b);
        else
            prt(qy(a, b)), putchar('\n');
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 31636 KB Output is correct
2 Correct 8 ms 31576 KB Output is correct
3 Correct 7 ms 31580 KB Output is correct
4 Correct 7 ms 31576 KB Output is correct
5 Correct 12 ms 31836 KB Output is correct
6 Correct 11 ms 31836 KB Output is correct
7 Correct 9 ms 31836 KB Output is correct
8 Correct 11 ms 31888 KB Output is correct
9 Correct 13 ms 31836 KB Output is correct
10 Correct 9 ms 31836 KB Output is correct
11 Correct 10 ms 31868 KB Output is correct
12 Correct 10 ms 31836 KB Output is correct
13 Correct 10 ms 31836 KB Output is correct
14 Correct 13 ms 31836 KB Output is correct
15 Correct 12 ms 31836 KB Output is correct
16 Correct 14 ms 31836 KB Output is correct
17 Correct 9 ms 31836 KB Output is correct
18 Correct 11 ms 31836 KB Output is correct
19 Correct 11 ms 31836 KB Output is correct
20 Correct 11 ms 31836 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 31576 KB Output is correct
2 Correct 148 ms 78248 KB Output is correct
3 Correct 124 ms 75944 KB Output is correct
4 Correct 121 ms 77908 KB Output is correct
5 Correct 128 ms 76492 KB Output is correct
6 Correct 107 ms 71252 KB Output is correct
7 Correct 113 ms 71252 KB Output is correct
8 Correct 146 ms 71248 KB Output is correct
9 Correct 104 ms 71276 KB Output is correct
10 Correct 135 ms 78676 KB Output is correct
11 Correct 112 ms 74596 KB Output is correct
12 Correct 106 ms 70996 KB Output is correct
13 Correct 111 ms 71024 KB Output is correct
14 Correct 113 ms 71900 KB Output is correct
15 Correct 130 ms 72064 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 31636 KB Output is correct
2 Correct 8 ms 31576 KB Output is correct
3 Correct 7 ms 31580 KB Output is correct
4 Correct 7 ms 31576 KB Output is correct
5 Correct 12 ms 31836 KB Output is correct
6 Correct 11 ms 31836 KB Output is correct
7 Correct 9 ms 31836 KB Output is correct
8 Correct 11 ms 31888 KB Output is correct
9 Correct 13 ms 31836 KB Output is correct
10 Correct 9 ms 31836 KB Output is correct
11 Correct 10 ms 31868 KB Output is correct
12 Correct 10 ms 31836 KB Output is correct
13 Correct 10 ms 31836 KB Output is correct
14 Correct 13 ms 31836 KB Output is correct
15 Correct 12 ms 31836 KB Output is correct
16 Correct 14 ms 31836 KB Output is correct
17 Correct 9 ms 31836 KB Output is correct
18 Correct 11 ms 31836 KB Output is correct
19 Correct 11 ms 31836 KB Output is correct
20 Correct 11 ms 31836 KB Output is correct
21 Correct 8 ms 31576 KB Output is correct
22 Correct 148 ms 78248 KB Output is correct
23 Correct 124 ms 75944 KB Output is correct
24 Correct 121 ms 77908 KB Output is correct
25 Correct 128 ms 76492 KB Output is correct
26 Correct 107 ms 71252 KB Output is correct
27 Correct 113 ms 71252 KB Output is correct
28 Correct 146 ms 71248 KB Output is correct
29 Correct 104 ms 71276 KB Output is correct
30 Correct 135 ms 78676 KB Output is correct
31 Correct 112 ms 74596 KB Output is correct
32 Correct 106 ms 70996 KB Output is correct
33 Correct 111 ms 71024 KB Output is correct
34 Correct 113 ms 71900 KB Output is correct
35 Correct 130 ms 72064 KB Output is correct
36 Correct 132 ms 78364 KB Output is correct
37 Correct 127 ms 76044 KB Output is correct
38 Correct 138 ms 76104 KB Output is correct
39 Correct 164 ms 77880 KB Output is correct
40 Correct 188 ms 76192 KB Output is correct
41 Correct 132 ms 71236 KB Output is correct
42 Correct 125 ms 71276 KB Output is correct
43 Correct 128 ms 71344 KB Output is correct
44 Correct 128 ms 71508 KB Output is correct
45 Correct 179 ms 78696 KB Output is correct
46 Correct 161 ms 78528 KB Output is correct
47 Correct 150 ms 74064 KB Output is correct
48 Correct 129 ms 71332 KB Output is correct
49 Correct 121 ms 71052 KB Output is correct
50 Correct 118 ms 71872 KB Output is correct
51 Correct 169 ms 71968 KB Output is correct
52 Correct 123 ms 71812 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 31576 KB Output is correct
2 Correct 148 ms 78248 KB Output is correct
3 Correct 124 ms 75944 KB Output is correct
4 Correct 121 ms 77908 KB Output is correct
5 Correct 128 ms 76492 KB Output is correct
6 Correct 107 ms 71252 KB Output is correct
7 Correct 113 ms 71252 KB Output is correct
8 Correct 146 ms 71248 KB Output is correct
9 Correct 104 ms 71276 KB Output is correct
10 Correct 135 ms 78676 KB Output is correct
11 Correct 112 ms 74596 KB Output is correct
12 Correct 106 ms 70996 KB Output is correct
13 Correct 111 ms 71024 KB Output is correct
14 Correct 113 ms 71900 KB Output is correct
15 Correct 130 ms 72064 KB Output is correct
16 Correct 6 ms 31580 KB Output is correct
17 Correct 1088 ms 76628 KB Output is correct
18 Correct 1091 ms 78956 KB Output is correct
19 Correct 1115 ms 76996 KB Output is correct
20 Correct 1170 ms 76584 KB Output is correct
21 Correct 1042 ms 76512 KB Output is correct
22 Correct 1156 ms 78340 KB Output is correct
23 Correct 1151 ms 76300 KB Output is correct
24 Correct 1177 ms 76812 KB Output is correct
25 Correct 1113 ms 76632 KB Output is correct
26 Correct 1126 ms 76884 KB Output is correct
27 Correct 831 ms 72156 KB Output is correct
28 Correct 847 ms 72260 KB Output is correct
29 Correct 859 ms 72176 KB Output is correct
30 Correct 1000 ms 71692 KB Output is correct
31 Correct 1025 ms 71952 KB Output is correct
32 Correct 1275 ms 75320 KB Output is correct
33 Correct 1413 ms 79252 KB Output is correct
34 Correct 1238 ms 74832 KB Output is correct
35 Correct 1177 ms 74404 KB Output is correct
36 Correct 1269 ms 79356 KB Output is correct
37 Correct 750 ms 71264 KB Output is correct
38 Correct 715 ms 71264 KB Output is correct
39 Correct 914 ms 72500 KB Output is correct
40 Correct 751 ms 72532 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 31576 KB Output is correct
2 Correct 148 ms 78248 KB Output is correct
3 Correct 124 ms 75944 KB Output is correct
4 Correct 121 ms 77908 KB Output is correct
5 Correct 128 ms 76492 KB Output is correct
6 Correct 107 ms 71252 KB Output is correct
7 Correct 113 ms 71252 KB Output is correct
8 Correct 146 ms 71248 KB Output is correct
9 Correct 104 ms 71276 KB Output is correct
10 Correct 135 ms 78676 KB Output is correct
11 Correct 112 ms 74596 KB Output is correct
12 Correct 106 ms 70996 KB Output is correct
13 Correct 111 ms 71024 KB Output is correct
14 Correct 113 ms 71900 KB Output is correct
15 Correct 130 ms 72064 KB Output is correct
16 Correct 7 ms 31580 KB Output is correct
17 Correct 1175 ms 78548 KB Output is correct
18 Correct 1255 ms 76692 KB Output is correct
19 Correct 1046 ms 76828 KB Output is correct
20 Correct 1169 ms 77144 KB Output is correct
21 Correct 1190 ms 78592 KB Output is correct
22 Correct 1342 ms 76448 KB Output is correct
23 Correct 1049 ms 76188 KB Output is correct
24 Correct 1235 ms 76896 KB Output is correct
25 Correct 1029 ms 76488 KB Output is correct
26 Correct 973 ms 71644 KB Output is correct
27 Correct 1102 ms 71508 KB Output is correct
28 Correct 1027 ms 73232 KB Output is correct
29 Correct 992 ms 71512 KB Output is correct
30 Correct 1095 ms 71556 KB Output is correct
31 Correct 1135 ms 73328 KB Output is correct
32 Correct 1220 ms 75180 KB Output is correct
33 Correct 1038 ms 75092 KB Output is correct
34 Correct 1196 ms 79048 KB Output is correct
35 Correct 1136 ms 78936 KB Output is correct
36 Correct 1156 ms 74924 KB Output is correct
37 Correct 1140 ms 73980 KB Output is correct
38 Correct 961 ms 73284 KB Output is correct
39 Correct 1031 ms 72288 KB Output is correct
40 Correct 852 ms 72408 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 31636 KB Output is correct
2 Correct 8 ms 31576 KB Output is correct
3 Correct 7 ms 31580 KB Output is correct
4 Correct 7 ms 31576 KB Output is correct
5 Correct 12 ms 31836 KB Output is correct
6 Correct 11 ms 31836 KB Output is correct
7 Correct 9 ms 31836 KB Output is correct
8 Correct 11 ms 31888 KB Output is correct
9 Correct 13 ms 31836 KB Output is correct
10 Correct 9 ms 31836 KB Output is correct
11 Correct 10 ms 31868 KB Output is correct
12 Correct 10 ms 31836 KB Output is correct
13 Correct 10 ms 31836 KB Output is correct
14 Correct 13 ms 31836 KB Output is correct
15 Correct 12 ms 31836 KB Output is correct
16 Correct 14 ms 31836 KB Output is correct
17 Correct 9 ms 31836 KB Output is correct
18 Correct 11 ms 31836 KB Output is correct
19 Correct 11 ms 31836 KB Output is correct
20 Correct 11 ms 31836 KB Output is correct
21 Correct 8 ms 31576 KB Output is correct
22 Correct 148 ms 78248 KB Output is correct
23 Correct 124 ms 75944 KB Output is correct
24 Correct 121 ms 77908 KB Output is correct
25 Correct 128 ms 76492 KB Output is correct
26 Correct 107 ms 71252 KB Output is correct
27 Correct 113 ms 71252 KB Output is correct
28 Correct 146 ms 71248 KB Output is correct
29 Correct 104 ms 71276 KB Output is correct
30 Correct 135 ms 78676 KB Output is correct
31 Correct 112 ms 74596 KB Output is correct
32 Correct 106 ms 70996 KB Output is correct
33 Correct 111 ms 71024 KB Output is correct
34 Correct 113 ms 71900 KB Output is correct
35 Correct 130 ms 72064 KB Output is correct
36 Correct 132 ms 78364 KB Output is correct
37 Correct 127 ms 76044 KB Output is correct
38 Correct 138 ms 76104 KB Output is correct
39 Correct 164 ms 77880 KB Output is correct
40 Correct 188 ms 76192 KB Output is correct
41 Correct 132 ms 71236 KB Output is correct
42 Correct 125 ms 71276 KB Output is correct
43 Correct 128 ms 71344 KB Output is correct
44 Correct 128 ms 71508 KB Output is correct
45 Correct 179 ms 78696 KB Output is correct
46 Correct 161 ms 78528 KB Output is correct
47 Correct 150 ms 74064 KB Output is correct
48 Correct 129 ms 71332 KB Output is correct
49 Correct 121 ms 71052 KB Output is correct
50 Correct 118 ms 71872 KB Output is correct
51 Correct 169 ms 71968 KB Output is correct
52 Correct 123 ms 71812 KB Output is correct
53 Correct 6 ms 31580 KB Output is correct
54 Correct 1088 ms 76628 KB Output is correct
55 Correct 1091 ms 78956 KB Output is correct
56 Correct 1115 ms 76996 KB Output is correct
57 Correct 1170 ms 76584 KB Output is correct
58 Correct 1042 ms 76512 KB Output is correct
59 Correct 1156 ms 78340 KB Output is correct
60 Correct 1151 ms 76300 KB Output is correct
61 Correct 1177 ms 76812 KB Output is correct
62 Correct 1113 ms 76632 KB Output is correct
63 Correct 1126 ms 76884 KB Output is correct
64 Correct 831 ms 72156 KB Output is correct
65 Correct 847 ms 72260 KB Output is correct
66 Correct 859 ms 72176 KB Output is correct
67 Correct 1000 ms 71692 KB Output is correct
68 Correct 1025 ms 71952 KB Output is correct
69 Correct 1275 ms 75320 KB Output is correct
70 Correct 1413 ms 79252 KB Output is correct
71 Correct 1238 ms 74832 KB Output is correct
72 Correct 1177 ms 74404 KB Output is correct
73 Correct 1269 ms 79356 KB Output is correct
74 Correct 750 ms 71264 KB Output is correct
75 Correct 715 ms 71264 KB Output is correct
76 Correct 914 ms 72500 KB Output is correct
77 Correct 751 ms 72532 KB Output is correct
78 Correct 7 ms 31580 KB Output is correct
79 Correct 1175 ms 78548 KB Output is correct
80 Correct 1255 ms 76692 KB Output is correct
81 Correct 1046 ms 76828 KB Output is correct
82 Correct 1169 ms 77144 KB Output is correct
83 Correct 1190 ms 78592 KB Output is correct
84 Correct 1342 ms 76448 KB Output is correct
85 Correct 1049 ms 76188 KB Output is correct
86 Correct 1235 ms 76896 KB Output is correct
87 Correct 1029 ms 76488 KB Output is correct
88 Correct 973 ms 71644 KB Output is correct
89 Correct 1102 ms 71508 KB Output is correct
90 Correct 1027 ms 73232 KB Output is correct
91 Correct 992 ms 71512 KB Output is correct
92 Correct 1095 ms 71556 KB Output is correct
93 Correct 1135 ms 73328 KB Output is correct
94 Correct 1220 ms 75180 KB Output is correct
95 Correct 1038 ms 75092 KB Output is correct
96 Correct 1196 ms 79048 KB Output is correct
97 Correct 1136 ms 78936 KB Output is correct
98 Correct 1156 ms 74924 KB Output is correct
99 Correct 1140 ms 73980 KB Output is correct
100 Correct 961 ms 73284 KB Output is correct
101 Correct 1031 ms 72288 KB Output is correct
102 Correct 852 ms 72408 KB Output is correct
103 Correct 1077 ms 76272 KB Output is correct
104 Correct 1206 ms 78672 KB Output is correct
105 Correct 1157 ms 76960 KB Output is correct
106 Correct 1146 ms 77092 KB Output is correct
107 Correct 1070 ms 76452 KB Output is correct
108 Correct 1270 ms 78344 KB Output is correct
109 Correct 1120 ms 76448 KB Output is correct
110 Correct 1117 ms 76748 KB Output is correct
111 Correct 1118 ms 77000 KB Output is correct
112 Correct 1126 ms 76808 KB Output is correct
113 Correct 1143 ms 71820 KB Output is correct
114 Correct 905 ms 72196 KB Output is correct
115 Correct 1187 ms 73400 KB Output is correct
116 Correct 1130 ms 73256 KB Output is correct
117 Correct 960 ms 71612 KB Output is correct
118 Correct 1131 ms 73624 KB Output is correct
119 Correct 1153 ms 71512 KB Output is correct
120 Correct 1180 ms 73308 KB Output is correct
121 Correct 1077 ms 73336 KB Output is correct
122 Correct 1213 ms 75160 KB Output is correct
123 Correct 1092 ms 74860 KB Output is correct
124 Correct 1147 ms 74504 KB Output is correct
125 Correct 1113 ms 74324 KB Output is correct
126 Correct 1142 ms 74408 KB Output is correct
127 Correct 1125 ms 73752 KB Output is correct
128 Correct 908 ms 72668 KB Output is correct
129 Correct 1139 ms 72344 KB Output is correct
130 Correct 977 ms 72384 KB Output is correct