oj.uz

Submission #958886

# Submission time Handle Problem Language Result Execution time Memory
958886 2024-04-07T02:42:58 Z gaga999 Fish 2 (JOI22_fish2) C++17
100 / 100
 1234 ms 80736 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);
    int num = 0;
    for (int i = 0, j = 0, p1 = 0; i <= slr; i++)
    {
        num += l.rnb[i];
        if (!num)
            continue;
        // db(i, l.rnb[i], "qsdihqiwd");
        while (l.rsm[i] >= r.lnd[j])
            j++;
        if (r.lsm[j] < l.rnd[i])
        {
            if (j == srl)
            {
                if (i == slr)
                    p.ans += num;
                else
                {
                    while (p.rsm[p1] < l.rsm[i] + r.sum)
                        p1++;
                    p.rnb[p1] += num;
                }
            }
            else if (i == slr)
                p.lnb[lower_bound(iter(p.lsm), r.lsm[j] + l.sum) - p.lsm.begin()] += num;
            num = 0;
        }
    }
    num = 0;
    for (int i = 0, j = 0, p2 = 0; i <= srl; i++)
    {
        num += r.lnb[i];
        if (!num)
            continue;
        while (r.lsm[i] >= l.rnd[j])
            j++;
        if (l.rsm[j] < r.lnd[i])
        {
            if (j == slr)
            {
                if (i == srl)
                    p.ans += num;
                else
                {
                    while (p.lsm[p2] < r.lsm[i] + l.sum)
                        p2++;
                    p.lnb[p2] += num;
                }
            }
            else if (i == srl)
                p.rnb[lower_bound(iter(p.rsm), l.rsm[j] + r.sum) - p.rsm.begin()] += num;
            num = 0;
        }
    }
    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 pp = tr[l++];
        // for (; l <= r; l++)
        //     pp = pp + tr[l];
        // return pp.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 = 1; i < n; i++)
    // {
    //     tr[i] = tr[i - 1] + tr[i], db(tr[i].ans, tr[i].sum);
    //     for (int p : tr[i].rnb)
    //         cerr << p << ' ';
    //     cerr << '\n';
    //     for (int p : tr[i].rsm)
    //         cerr << p << ' ';
    //     cerr << '\n';
    // }
    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 11 ms 31576 KB Output is correct
2 Correct 9 ms 31756 KB Output is correct
3 Correct 8 ms 31764 KB Output is correct
4 Correct 9 ms 31836 KB Output is correct
5 Correct 12 ms 31884 KB Output is correct
6 Correct 9 ms 32088 KB Output is correct
7 Correct 10 ms 31836 KB Output is correct
8 Correct 9 ms 31836 KB Output is correct
9 Correct 10 ms 31868 KB Output is correct
10 Correct 9 ms 31780 KB Output is correct
11 Correct 9 ms 31832 KB Output is correct
12 Correct 10 ms 31832 KB Output is correct
13 Correct 10 ms 31836 KB Output is correct
14 Correct 11 ms 31836 KB Output is correct
15 Correct 11 ms 31836 KB Output is correct
16 Correct 10 ms 31832 KB Output is correct
17 Correct 9 ms 31836 KB Output is correct
18 Correct 9 ms 31836 KB Output is correct
19 Correct 9 ms 31836 KB Output is correct
20 Correct 9 ms 31836 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 31580 KB Output is correct
2 Correct 115 ms 78580 KB Output is correct
3 Correct 116 ms 76444 KB Output is correct
4 Correct 115 ms 78416 KB Output is correct
5 Correct 113 ms 76484 KB Output is correct
6 Correct 109 ms 72020 KB Output is correct
7 Correct 117 ms 71584 KB Output is correct
8 Correct 138 ms 72024 KB Output is correct
9 Correct 109 ms 71580 KB Output is correct
10 Correct 122 ms 79188 KB Output is correct
11 Correct 118 ms 75276 KB Output is correct
12 Correct 106 ms 71208 KB Output is correct
13 Correct 104 ms 71400 KB Output is correct
14 Correct 130 ms 72276 KB Output is correct
15 Correct 116 ms 72528 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 31576 KB Output is correct
2 Correct 9 ms 31756 KB Output is correct
3 Correct 8 ms 31764 KB Output is correct
4 Correct 9 ms 31836 KB Output is correct
5 Correct 12 ms 31884 KB Output is correct
6 Correct 9 ms 32088 KB Output is correct
7 Correct 10 ms 31836 KB Output is correct
8 Correct 9 ms 31836 KB Output is correct
9 Correct 10 ms 31868 KB Output is correct
10 Correct 9 ms 31780 KB Output is correct
11 Correct 9 ms 31832 KB Output is correct
12 Correct 10 ms 31832 KB Output is correct
13 Correct 10 ms 31836 KB Output is correct
14 Correct 11 ms 31836 KB Output is correct
15 Correct 11 ms 31836 KB Output is correct
16 Correct 10 ms 31832 KB Output is correct
17 Correct 9 ms 31836 KB Output is correct
18 Correct 9 ms 31836 KB Output is correct
19 Correct 9 ms 31836 KB Output is correct
20 Correct 9 ms 31836 KB Output is correct
21 Correct 8 ms 31580 KB Output is correct
22 Correct 115 ms 78580 KB Output is correct
23 Correct 116 ms 76444 KB Output is correct
24 Correct 115 ms 78416 KB Output is correct
25 Correct 113 ms 76484 KB Output is correct
26 Correct 109 ms 72020 KB Output is correct
27 Correct 117 ms 71584 KB Output is correct
28 Correct 138 ms 72024 KB Output is correct
29 Correct 109 ms 71580 KB Output is correct
30 Correct 122 ms 79188 KB Output is correct
31 Correct 118 ms 75276 KB Output is correct
32 Correct 106 ms 71208 KB Output is correct
33 Correct 104 ms 71400 KB Output is correct
34 Correct 130 ms 72276 KB Output is correct
35 Correct 116 ms 72528 KB Output is correct
36 Correct 125 ms 79016 KB Output is correct
37 Correct 124 ms 76368 KB Output is correct
38 Correct 124 ms 76368 KB Output is correct
39 Correct 158 ms 78448 KB Output is correct
40 Correct 177 ms 76536 KB Output is correct
41 Correct 122 ms 72020 KB Output is correct
42 Correct 120 ms 72276 KB Output is correct
43 Correct 115 ms 71700 KB Output is correct
44 Correct 141 ms 71548 KB Output is correct
45 Correct 164 ms 79436 KB Output is correct
46 Correct 127 ms 79220 KB Output is correct
47 Correct 117 ms 74528 KB Output is correct
48 Correct 139 ms 71364 KB Output is correct
49 Correct 112 ms 71392 KB Output is correct
50 Correct 136 ms 72468 KB Output is correct
51 Correct 119 ms 72492 KB Output is correct
52 Correct 127 ms 72468 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 31580 KB Output is correct
2 Correct 115 ms 78580 KB Output is correct
3 Correct 116 ms 76444 KB Output is correct
4 Correct 115 ms 78416 KB Output is correct
5 Correct 113 ms 76484 KB Output is correct
6 Correct 109 ms 72020 KB Output is correct
7 Correct 117 ms 71584 KB Output is correct
8 Correct 138 ms 72024 KB Output is correct
9 Correct 109 ms 71580 KB Output is correct
10 Correct 122 ms 79188 KB Output is correct
11 Correct 118 ms 75276 KB Output is correct
12 Correct 106 ms 71208 KB Output is correct
13 Correct 104 ms 71400 KB Output is correct
14 Correct 130 ms 72276 KB Output is correct
15 Correct 116 ms 72528 KB Output is correct
16 Correct 7 ms 31576 KB Output is correct
17 Correct 1068 ms 77968 KB Output is correct
18 Correct 1064 ms 80424 KB Output is correct
19 Correct 947 ms 77584 KB Output is correct
20 Correct 981 ms 77512 KB Output is correct
21 Correct 921 ms 77504 KB Output is correct
22 Correct 1012 ms 79712 KB Output is correct
23 Correct 971 ms 77324 KB Output is correct
24 Correct 1046 ms 77788 KB Output is correct
25 Correct 930 ms 77680 KB Output is correct
26 Correct 993 ms 77612 KB Output is correct
27 Correct 831 ms 73496 KB Output is correct
28 Correct 832 ms 73612 KB Output is correct
29 Correct 865 ms 73552 KB Output is correct
30 Correct 951 ms 72852 KB Output is correct
31 Correct 1044 ms 72684 KB Output is correct
32 Correct 1140 ms 75656 KB Output is correct
33 Correct 1082 ms 80736 KB Output is correct
34 Correct 1115 ms 75640 KB Output is correct
35 Correct 928 ms 75312 KB Output is correct
36 Correct 1110 ms 80336 KB Output is correct
37 Correct 760 ms 72348 KB Output is correct
38 Correct 679 ms 72308 KB Output is correct
39 Correct 843 ms 73744 KB Output is correct
40 Correct 723 ms 73812 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 31580 KB Output is correct
2 Correct 115 ms 78580 KB Output is correct
3 Correct 116 ms 76444 KB Output is correct
4 Correct 115 ms 78416 KB Output is correct
5 Correct 113 ms 76484 KB Output is correct
6 Correct 109 ms 72020 KB Output is correct
7 Correct 117 ms 71584 KB Output is correct
8 Correct 138 ms 72024 KB Output is correct
9 Correct 109 ms 71580 KB Output is correct
10 Correct 122 ms 79188 KB Output is correct
11 Correct 118 ms 75276 KB Output is correct
12 Correct 106 ms 71208 KB Output is correct
13 Correct 104 ms 71400 KB Output is correct
14 Correct 130 ms 72276 KB Output is correct
15 Correct 116 ms 72528 KB Output is correct
16 Correct 7 ms 31580 KB Output is correct
17 Correct 973 ms 79444 KB Output is correct
18 Correct 1219 ms 77796 KB Output is correct
19 Correct 866 ms 77416 KB Output is correct
20 Correct 1089 ms 78328 KB Output is correct
21 Correct 1002 ms 79264 KB Output is correct
22 Correct 1177 ms 77684 KB Output is correct
23 Correct 871 ms 77380 KB Output is correct
24 Correct 1168 ms 77780 KB Output is correct
25 Correct 854 ms 77140 KB Output is correct
26 Correct 961 ms 73244 KB Output is correct
27 Correct 1068 ms 73060 KB Output is correct
28 Correct 1020 ms 74864 KB Output is correct
29 Correct 1035 ms 73012 KB Output is correct
30 Correct 1082 ms 72896 KB Output is correct
31 Correct 1081 ms 74712 KB Output is correct
32 Correct 1159 ms 76296 KB Output is correct
33 Correct 728 ms 75604 KB Output is correct
34 Correct 1187 ms 80192 KB Output is correct
35 Correct 768 ms 80100 KB Output is correct
36 Correct 1098 ms 75764 KB Output is correct
37 Correct 1064 ms 74732 KB Output is correct
38 Correct 917 ms 74836 KB Output is correct
39 Correct 987 ms 73640 KB Output is correct
40 Correct 797 ms 73860 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 31576 KB Output is correct
2 Correct 9 ms 31756 KB Output is correct
3 Correct 8 ms 31764 KB Output is correct
4 Correct 9 ms 31836 KB Output is correct
5 Correct 12 ms 31884 KB Output is correct
6 Correct 9 ms 32088 KB Output is correct
7 Correct 10 ms 31836 KB Output is correct
8 Correct 9 ms 31836 KB Output is correct
9 Correct 10 ms 31868 KB Output is correct
10 Correct 9 ms 31780 KB Output is correct
11 Correct 9 ms 31832 KB Output is correct
12 Correct 10 ms 31832 KB Output is correct
13 Correct 10 ms 31836 KB Output is correct
14 Correct 11 ms 31836 KB Output is correct
15 Correct 11 ms 31836 KB Output is correct
16 Correct 10 ms 31832 KB Output is correct
17 Correct 9 ms 31836 KB Output is correct
18 Correct 9 ms 31836 KB Output is correct
19 Correct 9 ms 31836 KB Output is correct
20 Correct 9 ms 31836 KB Output is correct
21 Correct 8 ms 31580 KB Output is correct
22 Correct 115 ms 78580 KB Output is correct
23 Correct 116 ms 76444 KB Output is correct
24 Correct 115 ms 78416 KB Output is correct
25 Correct 113 ms 76484 KB Output is correct
26 Correct 109 ms 72020 KB Output is correct
27 Correct 117 ms 71584 KB Output is correct
28 Correct 138 ms 72024 KB Output is correct
29 Correct 109 ms 71580 KB Output is correct
30 Correct 122 ms 79188 KB Output is correct
31 Correct 118 ms 75276 KB Output is correct
32 Correct 106 ms 71208 KB Output is correct
33 Correct 104 ms 71400 KB Output is correct
34 Correct 130 ms 72276 KB Output is correct
35 Correct 116 ms 72528 KB Output is correct
36 Correct 125 ms 79016 KB Output is correct
37 Correct 124 ms 76368 KB Output is correct
38 Correct 124 ms 76368 KB Output is correct
39 Correct 158 ms 78448 KB Output is correct
40 Correct 177 ms 76536 KB Output is correct
41 Correct 122 ms 72020 KB Output is correct
42 Correct 120 ms 72276 KB Output is correct
43 Correct 115 ms 71700 KB Output is correct
44 Correct 141 ms 71548 KB Output is correct
45 Correct 164 ms 79436 KB Output is correct
46 Correct 127 ms 79220 KB Output is correct
47 Correct 117 ms 74528 KB Output is correct
48 Correct 139 ms 71364 KB Output is correct
49 Correct 112 ms 71392 KB Output is correct
50 Correct 136 ms 72468 KB Output is correct
51 Correct 119 ms 72492 KB Output is correct
52 Correct 127 ms 72468 KB Output is correct
53 Correct 7 ms 31576 KB Output is correct
54 Correct 1068 ms 77968 KB Output is correct
55 Correct 1064 ms 80424 KB Output is correct
56 Correct 947 ms 77584 KB Output is correct
57 Correct 981 ms 77512 KB Output is correct
58 Correct 921 ms 77504 KB Output is correct
59 Correct 1012 ms 79712 KB Output is correct
60 Correct 971 ms 77324 KB Output is correct
61 Correct 1046 ms 77788 KB Output is correct
62 Correct 930 ms 77680 KB Output is correct
63 Correct 993 ms 77612 KB Output is correct
64 Correct 831 ms 73496 KB Output is correct
65 Correct 832 ms 73612 KB Output is correct
66 Correct 865 ms 73552 KB Output is correct
67 Correct 951 ms 72852 KB Output is correct
68 Correct 1044 ms 72684 KB Output is correct
69 Correct 1140 ms 75656 KB Output is correct
70 Correct 1082 ms 80736 KB Output is correct
71 Correct 1115 ms 75640 KB Output is correct
72 Correct 928 ms 75312 KB Output is correct
73 Correct 1110 ms 80336 KB Output is correct
74 Correct 760 ms 72348 KB Output is correct
75 Correct 679 ms 72308 KB Output is correct
76 Correct 843 ms 73744 KB Output is correct
77 Correct 723 ms 73812 KB Output is correct
78 Correct 7 ms 31580 KB Output is correct
79 Correct 973 ms 79444 KB Output is correct
80 Correct 1219 ms 77796 KB Output is correct
81 Correct 866 ms 77416 KB Output is correct
82 Correct 1089 ms 78328 KB Output is correct
83 Correct 1002 ms 79264 KB Output is correct
84 Correct 1177 ms 77684 KB Output is correct
85 Correct 871 ms 77380 KB Output is correct
86 Correct 1168 ms 77780 KB Output is correct
87 Correct 854 ms 77140 KB Output is correct
88 Correct 961 ms 73244 KB Output is correct
89 Correct 1068 ms 73060 KB Output is correct
90 Correct 1020 ms 74864 KB Output is correct
91 Correct 1035 ms 73012 KB Output is correct
92 Correct 1082 ms 72896 KB Output is correct
93 Correct 1081 ms 74712 KB Output is correct
94 Correct 1159 ms 76296 KB Output is correct
95 Correct 728 ms 75604 KB Output is correct
96 Correct 1187 ms 80192 KB Output is correct
97 Correct 768 ms 80100 KB Output is correct
98 Correct 1098 ms 75764 KB Output is correct
99 Correct 1064 ms 74732 KB Output is correct
100 Correct 917 ms 74836 KB Output is correct
101 Correct 987 ms 73640 KB Output is correct
102 Correct 797 ms 73860 KB Output is correct
103 Correct 912 ms 77212 KB Output is correct
104 Correct 1234 ms 79836 KB Output is correct
105 Correct 1002 ms 77892 KB Output is correct
106 Correct 1054 ms 77984 KB Output is correct
107 Correct 861 ms 77632 KB Output is correct
108 Correct 1218 ms 79544 KB Output is correct
109 Correct 948 ms 77412 KB Output is correct
110 Correct 1105 ms 77644 KB Output is correct
111 Correct 922 ms 77788 KB Output is correct
112 Correct 1038 ms 77724 KB Output is correct
113 Correct 1082 ms 73060 KB Output is correct
114 Correct 893 ms 73132 KB Output is correct
115 Correct 1158 ms 74380 KB Output is correct
116 Correct 1093 ms 74492 KB Output is correct
117 Correct 914 ms 71968 KB Output is correct
118 Correct 976 ms 73048 KB Output is correct
119 Correct 1085 ms 71324 KB Output is correct
120 Correct 1149 ms 73088 KB Output is correct
121 Correct 1030 ms 73588 KB Output is correct
122 Correct 1190 ms 75232 KB Output is correct
123 Correct 779 ms 74900 KB Output is correct
124 Correct 1069 ms 74464 KB Output is correct
125 Correct 886 ms 73984 KB Output is correct
126 Correct 1052 ms 74460 KB Output is correct
127 Correct 1110 ms 73472 KB Output is correct
128 Correct 840 ms 72628 KB Output is correct
129 Correct 1081 ms 72696 KB Output is correct
130 Correct 898 ms 72484 KB Output is correct