oj.uz

Submission #1014381

# Submission time Handle Problem Language Result Execution time Memory
1014381 2024-07-04T19:38:55 Z EJIC_B_KEDAX Dungeon 3 (JOI21_ho_t5) C++17
11 / 100
 677 ms 119472 KB 
#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<int, pair<int, int>>> ev;
    vector<pair<int, 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<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<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<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 131 ms 1880 KB Output is correct
2 Correct 27 ms 1880 KB Output is correct
3 Correct 28 ms 1872 KB Output is correct
4 Correct 141 ms 1824 KB Output is correct
5 Correct 28 ms 1880 KB Output is correct
6 Correct 85 ms 1704 KB Output is correct
7 Correct 27 ms 1884 KB Output is correct
8 Correct 30 ms 1880 KB Output is correct
9 Correct 21 ms 1880 KB Output is correct
10 Correct 134 ms 1884 KB Output is correct
11 Correct 122 ms 1880 KB Output is correct
12 Correct 87 ms 1692 KB Output is correct
13 Correct 130 ms 1884 KB Output is correct
14 Correct 25 ms 1880 KB Output is correct
15 Correct 34 ms 1880 KB Output is correct
16 Correct 25 ms 1892 KB Output is correct
17 Correct 144 ms 1884 KB Output is correct
18 Correct 148 ms 1884 KB Output is correct
19 Correct 93 ms 1692 KB Output is correct
20 Correct 9 ms 1932 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 103 ms 29448 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 677 ms 119472 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 1880 KB Output is correct
2 Correct 27 ms 1880 KB Output is correct
3 Correct 28 ms 1872 KB Output is correct
4 Correct 141 ms 1824 KB Output is correct
5 Correct 28 ms 1880 KB Output is correct
6 Correct 85 ms 1704 KB Output is correct
7 Correct 27 ms 1884 KB Output is correct
8 Correct 30 ms 1880 KB Output is correct
9 Correct 21 ms 1880 KB Output is correct
10 Correct 134 ms 1884 KB Output is correct
11 Correct 122 ms 1880 KB Output is correct
12 Correct 87 ms 1692 KB Output is correct
13 Correct 130 ms 1884 KB Output is correct
14 Correct 25 ms 1880 KB Output is correct
15 Correct 34 ms 1880 KB Output is correct
16 Correct 25 ms 1892 KB Output is correct
17 Correct 144 ms 1884 KB Output is correct
18 Correct 148 ms 1884 KB Output is correct
19 Correct 93 ms 1692 KB Output is correct
20 Correct 9 ms 1932 KB Output is correct
21 Incorrect 103 ms 29448 KB Output isn't correct
22 Halted 0 ms 0 KB -