Submission #1014385

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1014385	2024-07-04T19:48:42 Z	EJIC_B_KEDAX	Dungeon 3 (JOI21_ho_t5)	C++17	100 / 100	715 ms	118020 KB

Main

#include <bits/stdc++.h>
#include <immintrin.h>

using namespace std;

using ll = long long;
using ld = long double;
#define x first
#define y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

mt19937 mt(123);

void solve();
void init();

int32_t main() {
#ifndef LOCAL
    cin.tie(nullptr)->sync_with_stdio(false);
#endif
    cout << fixed << setprecision(30);
    init();
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}

struct segment_tree {
    vector<ll> st;
    int sz;
    segment_tree() = default;
    segment_tree(vector<int> a) {
        sz = 1;
        while (sz < a.size()) {
            sz <<= 1;
        }
        st.resize(2 * sz, 0);
        for (int i = 0; i < a.size(); i++) {
            st[sz + i] = a[i];
        }
        for (int i = sz - 1; i > 0; i--) {
            st[i] = st[2 * i] + st[2 * i + 1];
        }
    }
    void add(int i, ll x) {
        i += sz;
        while (i) {
            st[i] += x;
            i >>= 1;
        }
    }
    ll get(int l, int r) {
        l += sz;
        r += sz;
        ll res = 0;
        while (l <= r) {
            if (l & 1) {
                res += st[l++];
            }
            if (~r & 1) {
                res += st[r--];
            }
            l >>= 1;
            r >>= 1;
        }
        return res;
    }
};

struct mseg_tree {
    segment_tree def, step;
    int now_step;
    mseg_tree() = default;
    mseg_tree(int n) {
        now_step = 0;
        def = segment_tree(vector<int>(n, 0));
        step = segment_tree(vector<int>(n, 0));
    }
    void add_def(int i, int x) {
        def.add(i, x);
    }
    void add_step(int i, int x) {
        step.add(i, x);
        def.add(i, -1ll * x * now_step);
    }
    void next_step() {
        now_step++;
    }
    void set_step(int new_step) {
        now_step = new_step;
    }
    ll get(int l, int r) {
        return def.get(l, r) + now_step * step.get(l, r);
    }
};

struct sparse_max {
    using Type = pair<int, int>;
    vector<vector<Type>> sp;
    vector<int> p;
    sparse_max(const vector<Type>& a) {
        int n = a.size(), lg = 1;
        while ((1 << lg) < n) {
            lg++;
        }
        sp.resize(lg, vector<Type>(n));
        for (int i = 0; i < n; i++) {
            sp[0][i] = a[i];
        }
        for (int l = 1; l < lg; l++) {
            for (int i = 0; i <= n - (1 << l); i++) {
                sp[l][i] = max(sp[l - 1][i], sp[l - 1][i + (1 << (l - 1))]);
            }
        }
        int nw = 0;
        p.resize(n + 1, 0);
        for (int i = 1; i <= n; i++) {
            if ((1 << nw) * 2 < i) {
                nw++;
            }
            p[i] = nw;
        }
    }
    Type get(int l, int r) {
        int lev = p[r - l + 1];
        return max(sp[lev][l], sp[lev][r - (1 << lev) + 1]);
    }
};

struct segment_tree2 {
    vector<ll> st1, st2, lazy;
    int sz;
    segment_tree2(const vector<int>& a) {
        sz = 1;
        while (sz < a.size()) {
            sz <<= 1;
        }
        st1.resize(2 * sz);
        st2.resize(2 * sz);
        lazy.resize(2 * sz);
        for (int i = 0; i < 2 * sz; i++) {
            st1[i] = 0;
            st2[i] = 0;
            lazy[i] = 0;
        }
        for (int i = 0; i < a.size(); i++) {
            st1[sz + i] = a[i];
        }
        for (int i = sz - 1; i > 0; i--) {
            st1[i] = st1[2 * i] + st1[2 * i + 1];
        }
    }
    void push(int i) {
        if (i < sz && lazy[i]) {
            st2[2 * i] = st1[2 * i] * lazy[i];
            st2[2 * i + 1] = st1[2 * i + 1] * lazy[i];
            lazy[2 * i] = lazy[i];
            lazy[2 * i + 1] = lazy[i];
            lazy[i] = 0;
        }
    }
    void set(int l, int r, int v, int l1 = 0, int r1 = -1, int i = 1) {
        if (r1 == -1) {
            r1 += sz;
        }
        if (l1 >= l && r1 <= r) {
            lazy[i] = v;
            st2[i] = st1[i] * v;
            return;
        }
        if (l1 > r || r1 < l) {
            return;
        }
        push(i);
        set(l, r, v, l1, (l1 + r1) / 2, 2 * i);
        set(l, r, v, (l1 + r1) / 2 + 1, r1, 2 * i + 1);
        st2[i] = st2[2 * i] + st2[2 * i + 1];
    }

    ll get(int l, int r, int l1 = 0, int r1 = -1, int i = 1) {
        if (r1 == -1) {
            r1 += sz;
        }
        if (l1 >= l && r1 <= r) {
            return st2[i];
        }
        if (l1 > r || r1 < l) {
            return 0;
        }
        push(i);
        return get(l, r, l1, (l1 + r1) / 2, 2 * i) + get(l, r, (l1 + r1) / 2 + 1, r1, 2 * i + 1);
    }
};

void init() {}

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n), w(n), nxt(n), prv(n), start_time(q);
    vector<ll> pref(n + 1);
    for (int i = 0; i < n; i++) {
        cin >> w[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> a[i]; a[i] *= -1;
    }
    pref[0] = 0;
    for (int i = 0; i < n; i++) {
        pref[i + 1] = pref[i] + w[i];
    }
    mseg_tree st(n);
    for (int i = 0; i < n; i++) {
        st.add_step(i, a[i]);
    }
    vector<pair<int, int>> fsp(n), fsp2(n);
    for (int i = 0; i < n; i++) {
        fsp[i] = {a[i], -i};
        fsp2[i] = {w[i], 0};
    }
    sparse_max sp(fsp), spw(fsp2);
    vector<pair<ll, pair<int, int>>> ev;
    vector<pair<ll, int>> qu;
    vector<pair<int, int>> seg(q);
    vector<ll> ans(q);
    vector<vector<int>> start(n);
    for (int i = 0; i < q; i++) {
        int t, l, r;
        cin >> l >> r >> t; l--; r--; t--;
        qu.emplace_back(t, i);
        seg[i] = {l, r};
        start_time[i] = t;
        start[l].push_back(i);
    }
    vector<pair<int, int>> stack(1, {INT32_MAX, n});
    for (int i = n - 1; i >= 0; i--) {
        while (a[i] >= stack.back().x) {
            stack.pop_back();
        }
        nxt[i] = stack.back().y;
        stack.emplace_back(a[i], i);
    }
    stack.clear(); stack.emplace_back(INT32_MAX, -1);
    for (int i = 0; i < n; i++) {
        while (a[i] > stack.back().x) {
            stack.pop_back();
        }
        prv[i] = stack.back().y;
        stack.emplace_back(a[i], i);
    }
    for (int i = 0; i < n; i++) {
        ev.emplace_back(pref[nxt[i]] - pref[i], make_pair(i, -a[i]));
        if (prv[i] != -1) {
            ev.emplace_back(pref[i] - pref[prv[i]], make_pair(i, -a[i]));
            ev.emplace_back(pref[nxt[i]] - pref[prv[i]], make_pair(i, a[i]));
        }
    }
    sort(all(ev));
    sort(all(qu));
    int ptrev = 0, ptrqu = 0, t = 0;
    while (ptrqu < qu.size()) {
        while (ptrev < ev.size() && ev[ptrev].x == t) {
            st.add_step(ev[ptrev].y.x, ev[ptrev].y.y);
            ptrev++;
        }
        st.next_step();
        while (ptrqu < qu.size() && qu[ptrqu].x == t) {
            int i = qu[ptrqu++].y;
            auto [l, r] = seg[i];
            ll lans = 0, rans = 0;
            if (pref[l] + t < pref[r]) {
                {
                    int left = l, right = n;
                    while (right - left > 1) {
                        int mid = (right + left) / 2;
                        if (pref[mid] - pref[l] > t) {
                            right = mid;
                        } else {
                            left = mid;
                        }
                    }
                    auto [mx, mxi] = sp.get(l, left);
                    mxi *= -1;
                    lans = st.get(mxi + 1, n - 1);
                    ll lst = min(pref[mxi] + t, pref[nxt[mxi]] - 1);
                    lans += 1ll * (lst - pref[l] - t + 1) * mx;
                }
                if (r < n) {
                    int left = -1, right = r;
                    while (right - left > 1) {
                        int mid = (right + left) / 2;
                        if (pref[r] - pref[mid] > t) {
                            left = mid;
                        } else {
                            right = mid;
                        }
                    }
                    auto [mx, mxi] = sp.get(right, r);
                    mxi *= -1;
                    rans = st.get(mxi + 1, n - 1);
                    ll lst = min(pref[mxi] + t, pref[nxt[mxi]] - 1);
                    rans += 1ll * (lst - pref[r] + 1) * mx;
                }
            }
            ans[i] = lans - rans;
        }
        t++;
    }
    segment_tree2 st2(w);
    for (int pos = n - 1; pos >= 0; pos--) {
        st2.set(pos, nxt[pos] - 1, a[pos]);
        for (int i : start[pos]) {
            auto [l, r] = seg[i];
            int t = min(1ll * start_time[i], pref[r] - pref[l]);
            int left = l, right = n;
            while (right - left > 1) {
                int mid = (right + left) / 2;
                if (pref[mid] - pref[l] > t) {
                    right = mid;
                } else {
                    left = mid;
                }
            }
            ll weight = st2.get(left, left) / w[left];
            ans[i] += st2.get(l, left - 1) + weight * (pref[l] + t - pref[left]);
        }
    }
    for (int i = 0; i < q; i++) {
        if (spw.get(seg[i].x, seg[i].y - 1).x <= start_time[i] + 1) {
            cout << -ans[i] << '\n';
        } else {
            cout << "-1\n";
        }
    }
}

Compilation message

Main.cpp: In constructor 'segment_tree::segment_tree(std::vector<int>)':
Main.cpp:37:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         while (sz < a.size()) {
      |                ~~~^~~~~~~~~~
Main.cpp:41:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for (int i = 0; i < a.size(); i++) {
      |                         ~~^~~~~~~~~~
Main.cpp: In constructor 'segment_tree2::segment_tree2(const std::vector<int>&)':
Main.cpp:138:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |         while (sz < a.size()) {
      |                ~~~^~~~~~~~~~
Main.cpp:149:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |         for (int i = 0; i < a.size(); i++) {
      |                         ~~^~~~~~~~~~
Main.cpp: In function 'void solve()':
Main.cpp:264:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  264 |     while (ptrqu < qu.size()) {
      |            ~~~~~~^~~~~~~~~~~
Main.cpp:265:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  265 |         while (ptrev < ev.size() && ev[ptrev].x == t) {
      |                ~~~~~~^~~~~~~~~~~
Main.cpp:270:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  270 |         while (ptrqu < qu.size() && qu[ptrqu].x == t) {
      |                ~~~~~~^~~~~~~~~~~

Subtask #1

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	127 ms	1884 KB	Output is correct
2	Correct	27 ms	1880 KB	Output is correct
3	Correct	25 ms	1628 KB	Output is correct
4	Correct	150 ms	1884 KB	Output is correct
5	Correct	30 ms	1884 KB	Output is correct
6	Correct	99 ms	1872 KB	Output is correct
7	Correct	28 ms	1880 KB	Output is correct
8	Correct	31 ms	1880 KB	Output is correct
9	Correct	21 ms	1660 KB	Output is correct
10	Correct	135 ms	1884 KB	Output is correct
11	Correct	141 ms	1880 KB	Output is correct
12	Correct	101 ms	1660 KB	Output is correct
13	Correct	139 ms	1880 KB	Output is correct
14	Correct	41 ms	1884 KB	Output is correct
15	Correct	30 ms	1880 KB	Output is correct
16	Correct	30 ms	1880 KB	Output is correct
17	Correct	143 ms	1880 KB	Output is correct
18	Correct	138 ms	1880 KB	Output is correct
19	Correct	105 ms	1676 KB	Output is correct
20	Correct	7 ms	1884 KB	Output is correct

Subtask #2

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	90 ms	28152 KB	Output is correct
2	Correct	103 ms	27260 KB	Output is correct
3	Correct	106 ms	28156 KB	Output is correct
4	Correct	94 ms	26896 KB	Output is correct
5	Correct	111 ms	27296 KB	Output is correct
6	Correct	443 ms	115532 KB	Output is correct
7	Correct	450 ms	110964 KB	Output is correct
8	Correct	492 ms	118020 KB	Output is correct
9	Correct	460 ms	113212 KB	Output is correct
10	Correct	495 ms	116156 KB	Output is correct
11	Correct	491 ms	114308 KB	Output is correct
12	Correct	460 ms	113216 KB	Output is correct
13	Correct	477 ms	113792 KB	Output is correct
14	Correct	617 ms	113464 KB	Output is correct
15	Correct	542 ms	114696 KB	Output is correct

Subtask #3

31.0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	715 ms	114468 KB	Output is correct
2	Correct	698 ms	117988 KB	Output is correct
3	Correct	451 ms	113712 KB	Output is correct
4	Correct	545 ms	111828 KB	Output is correct
5	Correct	548 ms	115544 KB	Output is correct
6	Correct	714 ms	114524 KB	Output is correct
7	Correct	602 ms	113060 KB	Output is correct
8	Correct	566 ms	114292 KB	Output is correct
9	Correct	457 ms	111556 KB	Output is correct
10	Correct	437 ms	115396 KB	Output is correct
11	Correct	622 ms	117812 KB	Output is correct

Subtask #4

44.0 / 44.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	127 ms	1884 KB	Output is correct
2	Correct	27 ms	1880 KB	Output is correct
3	Correct	25 ms	1628 KB	Output is correct
4	Correct	150 ms	1884 KB	Output is correct
5	Correct	30 ms	1884 KB	Output is correct
6	Correct	99 ms	1872 KB	Output is correct
7	Correct	28 ms	1880 KB	Output is correct
8	Correct	31 ms	1880 KB	Output is correct
9	Correct	21 ms	1660 KB	Output is correct
10	Correct	135 ms	1884 KB	Output is correct
11	Correct	141 ms	1880 KB	Output is correct
12	Correct	101 ms	1660 KB	Output is correct
13	Correct	139 ms	1880 KB	Output is correct
14	Correct	41 ms	1884 KB	Output is correct
15	Correct	30 ms	1880 KB	Output is correct
16	Correct	30 ms	1880 KB	Output is correct
17	Correct	143 ms	1880 KB	Output is correct
18	Correct	138 ms	1880 KB	Output is correct
19	Correct	105 ms	1676 KB	Output is correct
20	Correct	7 ms	1884 KB	Output is correct
21	Correct	90 ms	28152 KB	Output is correct
22	Correct	103 ms	27260 KB	Output is correct
23	Correct	106 ms	28156 KB	Output is correct
24	Correct	94 ms	26896 KB	Output is correct
25	Correct	111 ms	27296 KB	Output is correct
26	Correct	443 ms	115532 KB	Output is correct
27	Correct	450 ms	110964 KB	Output is correct
28	Correct	492 ms	118020 KB	Output is correct
29	Correct	460 ms	113212 KB	Output is correct
30	Correct	495 ms	116156 KB	Output is correct
31	Correct	491 ms	114308 KB	Output is correct
32	Correct	460 ms	113216 KB	Output is correct
33	Correct	477 ms	113792 KB	Output is correct
34	Correct	617 ms	113464 KB	Output is correct
35	Correct	542 ms	114696 KB	Output is correct
36	Correct	715 ms	114468 KB	Output is correct
37	Correct	698 ms	117988 KB	Output is correct
38	Correct	451 ms	113712 KB	Output is correct
39	Correct	545 ms	111828 KB	Output is correct
40	Correct	548 ms	115544 KB	Output is correct
41	Correct	714 ms	114524 KB	Output is correct
42	Correct	602 ms	113060 KB	Output is correct
43	Correct	566 ms	114292 KB	Output is correct
44	Correct	457 ms	111556 KB	Output is correct
45	Correct	437 ms	115396 KB	Output is correct
46	Correct	622 ms	117812 KB	Output is correct
47	Correct	553 ms	113812 KB	Output is correct
48	Correct	660 ms	117524 KB	Output is correct
49	Correct	495 ms	113616 KB	Output is correct
50	Correct	645 ms	112816 KB	Output is correct
51	Correct	481 ms	114280 KB	Output is correct
52	Correct	538 ms	115496 KB	Output is correct
53	Correct	693 ms	113748 KB	Output is correct
54	Correct	643 ms	116820 KB	Output is correct
55	Correct	581 ms	113192 KB	Output is correct
56	Correct	445 ms	115456 KB	Output is correct
57	Correct	704 ms	117424 KB	Output is correct