Submission #971477

#	Time	Username	Problem	Language	Result	Execution time	Memory
971477		EJIC_B_KEDAX	Fish 2 (JOI22_fish2)	C++17	0 / 100	0 ms	348 KiB

fish2

#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();
    }
}

void init() {}

const int N = 100100;

struct node {
    vector<ll> sl, sr;
    vector<int> pl, pr, cl, cr;
    node(int a = -1) {
        sl.clear();
        sr.clear();
        pl.clear();
        pr.clear();
        cl.clear();
        cr.clear();
        sl.push_back(a);
        sr.push_back(a);
        pl.push_back(a);
        pr.push_back(a);
        cl.push_back(1);
        cr.push_back(1);
    }
    int cnt() {
        return cl.back();
    }
};

void merge(node& res, node a, node b) {
    res.cl = a.cl;
    res.sl = a.sl;
    res.pl = a.pl;
    res.cr = b.cr;
    res.sr = b.sr;
    res.pr = b.pr;
    ll s = 0;
    int c = 0, x = 0, y = 0;
    while (x < a.pr.size() || y < b.pl.size()) {
        if (y == b.pl.size() || (x < a.pr.size() && a.pr[x] < b.pl[y])) {
            if (s >= a.pr[x]) {
                s += a.sr[x];
                c += a.cr[x];
            } else if (y < b.pl.size()) {
                s += a.sr[x];
                c = a.cr[x];
            } else {
                break;
            }
            x++;
        } else {
            if (s >= b.pl[y]) {
                s += b.sl[y];
                c += b.cl[y];
            } else if (x < a.pr.size()) {
                s += b.sl[y];
                c = b.cl[y];
            } else {
                break;
            }
            y++;
        }
    }
    if (x == a.pr.size() && y == b.pl.size()) {
        res.sl.back() = s;
        res.sr.back() = s;
        res.cl.back() = c;
        res.cr.back() = c;
    } else if (x == a.pr.size()) {
        // res.cl.back() = s;
        // res.sl.back() = c;
        ll ss = s;
        for (int i = 0; i + 1 < a.pl.size(); i++) {
            s += a.sl[i];
        }
        for (; y < b.pl.size(); y++) {
            res.cl.back() = c;
            res.sl.back() = ss;
            if (s < b.pl[y]) {
                res.cl.push_back(0);
                res.sl.push_back(0);
                res.pl.push_back(b.pl[y]);
                ss = 0;
                c = 0;
            }
            s += b.sl[y];
            ss += b.sl[y];
            c += b.cl[y];
        }
        res.cl.back() = c;
        res.sl.back() = ss;
        res.cr.back() = c;
        res.cr.back() = ss;
    } else {
        ll ss = s;
        for (int i = 0; i + 1 < b.pr.size(); i++) {
            s += b.sr[i];
        }
        for (; x < a.pr.size(); x++) {
            res.cr.back() = c;
            res.sr.back() = ss;
            if (s < a.pr[x]) {
                res.cr.push_back(0);
                res.sr.push_back(0);
                res.pr.push_back(a.pr[x]);
                ss = 0;
                c = 0;
            }
            s += a.sr[x];
            ss += a.sr[x];
            c += a.cr[x];
        }
        res.cl.back() = c;
        res.sl.back() = ss;
        res.cr.back() = c;
        res.sr.back() = ss;
    }
}

struct segment_tree {
    vector<node> st;
    size_t size;
    segment_tree(int sz = N) {
        size = sz;
        st.resize(2 * size);
    }
    void update(int i, int x) {
        i += size;
        st[i] = node(x);
        i >>= 1;
        while (i) {
            merge(st[i], st[2 * i], st[2 * i + 1]);
            i >>= 1;
        }
    }
    int get(int l, int r) {
        node res_l, res_r;
        l += size;
        r += size;
        while (l <= r) {
            if (l & 1) {
                if (res_l.sl[0] == -1) {
                    res_l = st[l++];
                } else {
                    merge(res_l, res_l, st[l]);
                    l++;
                }
            }
            if (~r & 1) {
                if (res_r.sl[0] == -1) {
                    res_r = st[r--];
                } else {
                    merge(res_r, st[r], res_r);
                    r--;
                }
            }
            l >>= 1;
            r >>= 1;
        }
        node res;
        merge(res, res_l, res_r);
        return res.cnt();
    }
};

void solve() {
    int n;
    cin >> n;
    segment_tree st(n);
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        st.update(i, x);
    }
    int q;
    cin >> q;
    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int x, y;
            cin >> x >> y; x--;
            st.update(x, y);
        } else {
            int l, r;
            cin >> l >> r; l--; r--;
            cout << st.get(l, r) << '\n';
        }
    }
}

Compilation message (stderr)

fish2.cpp: In function 'void merge(node&, node, node)':
fish2.cpp:66:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     while (x < a.pr.size() || y < b.pl.size()) {
      |              ^
fish2.cpp:66:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     while (x < a.pr.size() || y < b.pl.size()) {
      |                                 ^
fish2.cpp:67:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         if (y == b.pl.size() || (x < a.pr.size() && a.pr[x] < b.pl[y])) {
      |               ^
fish2.cpp:67:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         if (y == b.pl.size() || (x < a.pr.size() && a.pr[x] < b.pl[y])) {
      |                                    ^
fish2.cpp:71:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |             } else if (y < b.pl.size()) {
      |                          ^
fish2.cpp:82:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |             } else if (x < a.pr.size()) {
      |                          ^
fish2.cpp:91:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     if (x == a.pr.size() && y == b.pl.size()) {
      |           ^
fish2.cpp:91:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     if (x == a.pr.size() && y == b.pl.size()) {
      |                               ^
fish2.cpp:96:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     } else if (x == a.pr.size()) {
      |                  ^
fish2.cpp:100:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |         for (int i = 0; i + 1 < a.pl.size(); i++) {
      |                         ~~~~~~^~~~~~~~~~~~~
fish2.cpp:103:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |         for (; y < b.pl.size(); y++) {
      |                  ^
fish2.cpp:123:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |         for (int i = 0; i + 1 < b.pr.size(); i++) {
      |                         ~~~~~~^~~~~~~~~~~~~
fish2.cpp:126:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |         for (; x < a.pr.size(); x++) {
      |                  ^

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 12
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 17