Submission #559959

#	Time	Username	Problem	Language	Result	Execution time	Memory
559959		two_sides	Fish 2 (JOI22_fish2)	C++17	0 / 100	5 ms	9684 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.push_back(c.rig.back());
    else if (c.rig.empty())
        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]);
    }
}

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:35:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for (int i = 0, j = 0; i < a.rig.size(); i++) {
      |                            ~~^~~~~~~~~~~~~~
fish2.cpp:36:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         while (j < b.lef.size() && a.rig[i].sum +
      |                ~~^~~~~~~~~~~~~~
fish2.cpp:39:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         if (j && i + 1 < a.rig.size() &&
      |                  ~~~~~~^~~~~~~~~~~~~~
fish2.cpp:45:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         if (j == b.lef.size()) {
      |             ~~^~~~~~~~~~~~~~~
fish2.cpp:51:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for (int i = 0, j = 0; i < b.lef.size(); i++) {
      |                            ~~^~~~~~~~~~~~~~
fish2.cpp:52:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         while (j < a.rig.size() && b.lef[i].sum +
      |                ~~^~~~~~~~~~~~~~
fish2.cpp:55:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         if (j && i + 1 < b.lef.size() &&
      |                  ~~~~~~^~~~~~~~~~~~~~
fish2.cpp:61:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         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