Submission #559994

#	Time	Username	Problem	Language	Result	Execution time	Memory
559994		two_sides	Fish 2 (JOI22_fish2)	C++17	0 / 100	62 ms	30812 KiB

fish2

#include <bits/stdc++.h>

using namespace std;

#define il i + 1
#define ir i + (m - l + 1) * 2

using ll = long long;

struct item {
    int pos, cnt; ll sum;
    
    item(int pos, int cnt, ll sum):
    pos(pos), cnt(cnt), sum(sum) {}
};

struct node {
    vector<item> lef, rig;
};

const int N = 100005;

int val[N]; node seg[N * 2];
node res; int lo, hi;

void merge(int m, node a, node b, node &c) {
    c.lef.clear(); c.rig.clear();
    for (auto u : a.lef)
        if (u.sum < val[u.pos + 1])
            c.lef.push_back(u);

    for (auto u : b.rig)
        if (u.sum < val[u.pos - 1])
            c.rig.push_back(u);
    
    for (int i = 0, j = 0; i < a.rig.size(); i++) {
        while (j < b.lef.size() && a.rig[i].sum +
        (j ? b.lef[j - 1].sum : 0) >=
        val[j ? b.lef[j - 1].pos + 1 : m + 1]) j++;
        if (j && i + 1 < a.rig.size() &&
        a.rig[i].sum + b.lef[j - 1].sum >=
        val[a.rig[i].pos - 1]) {
            a.rig[i + 1].cnt += a.rig[i].cnt;
            continue;
        }
        if (j == b.lef.size()) {
            item u = a.rig[i];
            u.sum += b.lef[j - 1].sum;
            c.rig.push_back(u);
        }
    }
    for (int i = 0, j = 0; i < b.lef.size(); i++) {
        while (j < a.rig.size() && b.lef[i].sum +
        (j ? a.rig[j - 1].sum : 0) >=
        val[j ? a.rig[j - 1].pos - 1 : m]) j++;
        if (j && i + 1 < b.lef.size() &&
        b.lef[i].sum + a.rig[j - 1].sum >=
        val[b.lef[i].pos + 1]) {
            b.lef[i + 1].cnt += b.lef[i].cnt;
            continue;
        }
        if (j == a.rig.size()) {
            item u = b.lef[i];
            u.sum += a.rig[j - 1].sum;
            c.lef.push_back(u);
        }
    }
    if (c.lef.empty() || c.lef.back().pos != b.lef.back().pos)
        c.lef.push_back(c.rig.back());
    else if (c.rig.empty() || c.rig.back().pos != a.rig.back().pos)
        c.rig.push_back(c.lef.back());
    else c.lef.back().cnt = c.rig.back().cnt
        = c.lef.back().cnt + c.rig.back().cnt;
    c.lef.back().pos = b.lef.back().pos;
    c.rig.back().pos = a.rig.back().pos;

}

void build(int i, int l, int r) {
    if (l == r) {
        seg[i].lef.emplace_back(l, 1, val[l]);
        seg[i].rig.emplace_back(l, 1, val[l]);
    } else {
        int m = (l + r) / 2;
        build(il, l, m); build(ir, m + 1, r);
        merge(m, seg[il], seg[ir], seg[i]);
        
        // cerr<<l<<' '<<m<<' '<<r<<'\n';
        // for (auto u : seg[i].lef)
            // cerr<<u.pos<<' '<<u.cnt<<'\n';
        // cerr<<'\n';
        // for (auto u : seg[i].rig)
            // cerr<<u.pos<<' '<<u.cnt<<'\n';
        // cerr<<'\n';
    }
}

void update(int i, int l, int r, int p) {
    if (l == r) {
        seg[i].lef[0] = {l, 1, val[l]};
        seg[i].rig[0] = {l, 1, val[l]};
    } else {
        int m = (l + r) / 2;
        if (m >= p) update(il, l, m, p);
        else update(ir, m + 1, r, p);
        merge(m, seg[il], seg[ir], seg[i]);
    }
}

void get(int i, int l, int r) {
    if (l >= lo && r <= hi) {
        if (l == lo) res = seg[i];
        else merge(l - 1, res, seg[i], res);
    } else {
        int m = (l + r) / 2;
        if (m >= lo) get(il, l, m);
        if (m < hi) get(ir, m + 1, r);
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n; cin >> n;
    for (int i = 1; i <= n; i++) 
        cin >> val[i];
    build(1, 1, n);
    int q; cin >> q;
    while (q--) {
        int cmd; cin >> cmd;
        if (cmd == 1) {
            int p; cin >> p >> val[p];
            update(1, 1, n, p);
        } else {
            cin >> lo >> hi; get(1, 1, n);
            cout << res.lef.back().cnt << '\n';
        }
    }
}

Compilation message (stderr)

fish2.cpp: In function 'void merge(int, node, node, node&)':
fish2.cpp:36:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for (int i = 0, j = 0; i < a.rig.size(); i++) {
      |                            ~~^~~~~~~~~~~~~~
fish2.cpp:37:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         while (j < b.lef.size() && a.rig[i].sum +
      |                ~~^~~~~~~~~~~~~~
fish2.cpp:40:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         if (j && i + 1 < a.rig.size() &&
      |                  ~~~~~~^~~~~~~~~~~~~~
fish2.cpp:46:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         if (j == b.lef.size()) {
      |             ~~^~~~~~~~~~~~~~~
fish2.cpp:52:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for (int i = 0, j = 0; i < b.lef.size(); i++) {
      |                            ~~^~~~~~~~~~~~~~
fish2.cpp:53:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         while (j < a.rig.size() && b.lef[i].sum +
      |                ~~^~~~~~~~~~~~~~
fish2.cpp:56:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         if (j && i + 1 < b.lef.size() &&
      |                  ~~~~~~^~~~~~~~~~~~~~
fish2.cpp:62:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         if (j == a.rig.size()) {
      |             ~~^~~~~~~~~~~~~~~

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