oj.uz

답안 #1014382

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1014382 2024-07-04T19:40:30 Z EJIC_B_KEDAX Dungeon 3 (JOI21_ho_t5) C++17
100 / 100
 729 ms 197624 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();
    }
}

#define int ll

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<long long int>)':
Main.cpp:39:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         while (sz < a.size()) {
      |                ~~~^~~~~~~~~~
Main.cpp:43:27: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         for (int i = 0; i < a.size(); i++) {
      |                         ~~^~~~~~~~~~
Main.cpp: In constructor 'segment_tree2::segment_tree2(const std::vector<long long int>&)':
Main.cpp:140:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |         while (sz < a.size()) {
      |                ~~~^~~~~~~~~~
Main.cpp:151:27: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |         for (int i = 0; i < a.size(); i++) {
      |                         ~~^~~~~~~~~~
Main.cpp: In function 'void solve()':
Main.cpp:266:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  266 |     while (ptrqu < qu.size()) {
      |            ~~~~~~^~~~~~~~~~~
Main.cpp:267:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  267 |         while (ptrev < ev.size() && ev[ptrev].x == t) {
      |                ~~~~~~^~~~~~~~~~~
Main.cpp:272:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  272 |         while (ptrqu < qu.size() && qu[ptrqu].x == t) {
      |                ~~~~~~^~~~~~~~~~~

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 105 ms 2728 KB Output is correct
2 Correct 25 ms 2888 KB Output is correct
3 Correct 25 ms 2644 KB Output is correct
4 Correct 108 ms 2868 KB Output is correct
5 Correct 25 ms 2892 KB Output is correct
6 Correct 113 ms 2580 KB Output is correct
7 Correct 26 ms 2868 KB Output is correct
8 Correct 25 ms 2804 KB Output is correct
9 Correct 25 ms 2652 KB Output is correct
10 Correct 117 ms 2868 KB Output is correct
11 Correct 142 ms 2888 KB Output is correct
12 Correct 98 ms 2580 KB Output is correct
13 Correct 95 ms 2868 KB Output is correct
14 Correct 25 ms 2892 KB Output is correct
15 Correct 22 ms 3144 KB Output is correct
16 Correct 22 ms 2888 KB Output is correct
17 Correct 115 ms 2916 KB Output is correct
18 Correct 100 ms 2888 KB Output is correct
19 Correct 89 ms 2640 KB Output is correct
20 Correct 5 ms 2816 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 108 ms 46016 KB Output is correct
2 Correct 109 ms 45496 KB Output is correct
3 Correct 110 ms 46352 KB Output is correct
4 Correct 104 ms 43468 KB Output is correct
5 Correct 124 ms 45752 KB Output is correct
6 Correct 470 ms 191776 KB Output is correct
7 Correct 517 ms 186928 KB Output is correct
8 Correct 544 ms 197096 KB Output is correct
9 Correct 474 ms 187696 KB Output is correct
10 Correct 538 ms 192920 KB Output is correct
11 Correct 555 ms 189456 KB Output is correct
12 Correct 512 ms 187532 KB Output is correct
13 Correct 505 ms 193960 KB Output is correct
14 Correct 601 ms 194056 KB Output is correct
15 Correct 462 ms 194804 KB Output is correct

Subtask #3
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 684 ms 193272 KB Output is correct
2 Correct 623 ms 196628 KB Output is correct
3 Correct 558 ms 188188 KB Output is correct
4 Correct 616 ms 188280 KB Output is correct
5 Correct 519 ms 191660 KB Output is correct
6 Correct 629 ms 189856 KB Output is correct
7 Correct 628 ms 192060 KB Output is correct
8 Correct 568 ms 189208 KB Output is correct
9 Correct 517 ms 186544 KB Output is correct
10 Correct 418 ms 194300 KB Output is correct
11 Correct 616 ms 197624 KB Output is correct

Subtask #4
44.0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 105 ms 2728 KB Output is correct
2 Correct 25 ms 2888 KB Output is correct
3 Correct 25 ms 2644 KB Output is correct
4 Correct 108 ms 2868 KB Output is correct
5 Correct 25 ms 2892 KB Output is correct
6 Correct 113 ms 2580 KB Output is correct
7 Correct 26 ms 2868 KB Output is correct
8 Correct 25 ms 2804 KB Output is correct
9 Correct 25 ms 2652 KB Output is correct
10 Correct 117 ms 2868 KB Output is correct
11 Correct 142 ms 2888 KB Output is correct
12 Correct 98 ms 2580 KB Output is correct
13 Correct 95 ms 2868 KB Output is correct
14 Correct 25 ms 2892 KB Output is correct
15 Correct 22 ms 3144 KB Output is correct
16 Correct 22 ms 2888 KB Output is correct
17 Correct 115 ms 2916 KB Output is correct
18 Correct 100 ms 2888 KB Output is correct
19 Correct 89 ms 2640 KB Output is correct
20 Correct 5 ms 2816 KB Output is correct
21 Correct 108 ms 46016 KB Output is correct
22 Correct 109 ms 45496 KB Output is correct
23 Correct 110 ms 46352 KB Output is correct
24 Correct 104 ms 43468 KB Output is correct
25 Correct 124 ms 45752 KB Output is correct
26 Correct 470 ms 191776 KB Output is correct
27 Correct 517 ms 186928 KB Output is correct
28 Correct 544 ms 197096 KB Output is correct
29 Correct 474 ms 187696 KB Output is correct
30 Correct 538 ms 192920 KB Output is correct
31 Correct 555 ms 189456 KB Output is correct
32 Correct 512 ms 187532 KB Output is correct
33 Correct 505 ms 193960 KB Output is correct
34 Correct 601 ms 194056 KB Output is correct
35 Correct 462 ms 194804 KB Output is correct
36 Correct 684 ms 193272 KB Output is correct
37 Correct 623 ms 196628 KB Output is correct
38 Correct 558 ms 188188 KB Output is correct
39 Correct 616 ms 188280 KB Output is correct
40 Correct 519 ms 191660 KB Output is correct
41 Correct 629 ms 189856 KB Output is correct
42 Correct 628 ms 192060 KB Output is correct
43 Correct 568 ms 189208 KB Output is correct
44 Correct 517 ms 186544 KB Output is correct
45 Correct 418 ms 194300 KB Output is correct
46 Correct 616 ms 197624 KB Output is correct
47 Correct 605 ms 193528 KB Output is correct
48 Correct 669 ms 196496 KB Output is correct
49 Correct 512 ms 187640 KB Output is correct
50 Correct 598 ms 190572 KB Output is correct
51 Correct 530 ms 189704 KB Output is correct
52 Correct 572 ms 191568 KB Output is correct
53 Correct 666 ms 193536 KB Output is correct
54 Correct 668 ms 195620 KB Output is correct
55 Correct 602 ms 187404 KB Output is correct
56 Correct 428 ms 194552 KB Output is correct
57 Correct 729 ms 197368 KB Output is correct