Submission #962368

#	Time	Username	Problem	Language	Result	Execution time	Memory
962368		alextodoran	Fish 2 (JOI22_fish2)	C++17	100 / 100	2004 ms	48120 KiB

fish2

/**
 _  _   __  _ _ _  _  _ _
 |a  ||t  ||o    d | |o  |
| __    _| | _ | __|  _ |
| __ |/_  | __  /__\ / _\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 100000;

int N;
ll A[N_MAX + 2];

struct Block {
    int l, r;
    bool contains (int i) {
        return (l <= i && i <= r);
    }
};

struct SegInfo {
    ll val; int cnt;
    ll lazy;
    void add (const ll &x) {
        val += x; lazy += x;
    }
};
SegInfo operator + (const SegInfo &A, const SegInfo &B) {
    SegInfo C;
    C.val = min(A.val, B.val);
    C.cnt = (C.val == A.val ? A.cnt : 0) + (C.val == B.val ? B.cnt : 0);
    C.lazy = 0;
    return C;
}
void build_tree (SegInfo seg_tree[], int node, int l, int r) {
    seg_tree[node].cnt = r - l + 1;
    if (l != r) {
        int mid = (l + r) / 2;
        int left = node * 2, right = node * 2 + 1;
        build_tree(seg_tree, left, l, mid);
        build_tree(seg_tree, right, mid + 1, r);
    }
}
void build_tree (SegInfo seg_tree[]) {
    build_tree(seg_tree, 1, 1, N);
}
void update_tree (SegInfo seg_tree[], int node, int l, int r, int ul, int ur, ll x) {
    if (ul <= l && r <= ur) {
        seg_tree[node].add(x);
        return;
    }
    int mid = (l + r) / 2;
    int left = node * 2, right = node * 2 + 1;
    seg_tree[left].add(seg_tree[node].lazy);
    seg_tree[right].add(seg_tree[node].lazy);
    seg_tree[node].lazy = 0;
    if (ul <= mid) {
        update_tree(seg_tree, left, l, mid, ul, ur, x);
    }
    if (mid + 1 <= ur) {
        update_tree(seg_tree, right, mid + 1, r, ul, ur, x);
    }
    seg_tree[node] = seg_tree[left] + seg_tree[right];
}
void update_tree (SegInfo seg_tree[], int ul, int ur, ll x) {
    update_tree(seg_tree, 1, 1, N, ul, ur, x);
}
void update_tree (SegInfo seg_tree[], int i, ll x) {
    update_tree(seg_tree, 1, 1, N, i, i, x);
}
SegInfo query_cnt (SegInfo seg_tree[], int node, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
        return seg_tree[node];
    }
    int mid = (l + r) / 2;
    int left = node * 2, right = node * 2 + 1;
    seg_tree[left].add(seg_tree[node].lazy);
    seg_tree[right].add(seg_tree[node].lazy);
    seg_tree[node].lazy = 0;
    if (ql <= mid && mid + 1 <= qr) {
        return query_cnt(seg_tree, left, l, mid, ql, qr)
             + query_cnt(seg_tree, right, mid + 1, r, ql, qr);
    } else if (qr <= mid) {
        return query_cnt(seg_tree, left, l, mid, ql, qr);
    } else {
        return query_cnt(seg_tree, right, mid + 1, r, ql, qr);
    }
}
int query_cnt (SegInfo seg_tree[], int ql, int qr) {
    return query_cnt(seg_tree, 1, 1, N, ql, qr).cnt;
}
int query_last (SegInfo seg_tree[], int node, int l, int r, int i, ll val) {
    if (seg_tree[node].val > val) {
        return 0;
    }
    if (l == r) {
        return l;
    }
    int mid = (l + r) / 2;
    int left = node * 2, right = node * 2 + 1;
    seg_tree[left].add(seg_tree[node].lazy);
    seg_tree[right].add(seg_tree[node].lazy);
    seg_tree[node].lazy = 0;
    if (i <= mid) {
        return query_last(seg_tree, left, l, mid, i, val);
    } else {
        int j = query_last(seg_tree, right, mid + 1, r, i, val);
        return (j != 0 ? j : query_last(seg_tree, left, l, mid, i, val));
    }
}
int query_last (SegInfo seg_tree[], int i, ll val) {
    return query_last(seg_tree, 1, 1, N, i, val);
}
int query_first (SegInfo seg_tree[], int node, int l, int r, int i, ll val) {
    if (seg_tree[node].val > val) {
        return N + 1;
    }
    if (l == r) {
        return l;
    }
    int mid = (l + r) / 2;
    int left = node * 2, right = node * 2 + 1;
    seg_tree[left].add(seg_tree[node].lazy);
    seg_tree[right].add(seg_tree[node].lazy);
    seg_tree[node].lazy = 0;
    if (mid + 1 <= i) {
        return query_first(seg_tree, right, mid + 1, r, i, val);
    } else {
        int j = query_first(seg_tree, left, l, mid, i, val);
        return (j != N + 1 ? j : query_first(seg_tree, right, mid + 1, r, i, val));
    }
}
int query_first (SegInfo seg_tree[], int i, ll val) {
    return query_first(seg_tree, 1, 1, N, i, val);
}

SegInfo min_tree[N_MAX * 4 + 2];

void add_block (Block b) {
    update_tree(min_tree, b.l, b.r, +1);
}
void del_block (Block b) {
    update_tree(min_tree, b.l, b.r, -1);
}

vector <Block> block_tree[N_MAX * 4 + 2];

void add_blocks (int node, int l, int r, int i, vector <Block> &blocks) {
    if (l != r) {
        int mid = (l + r) / 2;
        int left = node * 2, right = node * 2 + 1;
        if (i <= mid) {
            add_blocks(left, l, mid, i, blocks);
        } else {
            add_blocks(right, mid + 1, r, i, blocks);
        }
    }
    while (blocks.empty() == false && l <= blocks.back().l && blocks.back().r <= r) {
        add_block(blocks.back());
        block_tree[node].push_back(blocks.back());
        blocks.pop_back();
    }
}
void add_blocks (int i, vector <Block> &blocks) {
    add_blocks(1, 1, N, i, blocks);
}
void del_blocks (int node, int l, int r, int i) {
    while (block_tree[node].empty() == false && block_tree[node].back().contains(i)) {
        del_block(block_tree[node].back());
        block_tree[node].pop_back();
    }
    if (l != r) {
        int mid = (l + r) / 2;
        int left = node * 2, right = node * 2 + 1;
        if (i <= mid) {
            del_blocks(left, l, mid, i);
        } else {
            del_blocks(right, mid + 1, r, i);
        }
    }
}
void del_blocks (int i) {
    del_blocks(1, 1, N, i);
}

ll Fen[N_MAX + 2];
void update_Fen (int pos, ll val) {
    for (int i = pos; i <= N; i += i & -i) {
        Fen[i] += val;
    }
}
ll query_Fen (int pos) {
    ll sum = 0;
    for (int i = pos; i >= 1; i -= i & -i) {
        sum += Fen[i];
    }
    return sum;
}
ll query_Fen (int l, int r) {
    return (l <= r ? query_Fen(r) - query_Fen(l - 1) : 0);
}

SegInfo max_tree[N_MAX * 4];

vector <Block> find_blocks (int i) {
    vector <Block> blocks;
    vector <int> ls, rs;
    int j; ll sum;
    j = i; sum = 0;
    while (j > 1) {
        sum += A[j];
        j = query_last(max_tree, j - 1, -(sum + 1));
        ls.push_back(j + 1);
    }
    j = i; sum = 0;
    while (j < N) {
        sum += A[j];
        j = query_first(max_tree, j + 1, -(sum + 1));
        rs.push_back(j - 1);
    }
    for (int l : ls) {
        for (int r : rs) {
            ll sum = query_Fen(l, r);
            if (sum < A[l - 1] && sum < A[r + 1]) {
                blocks.push_back(Block{l, r});
            }
        }
    }
    return blocks;
}

void add_blocks (int i) {
    vector <Block> blocks = find_blocks(i);
    reverse(blocks.begin(), blocks.end());
    add_blocks(i, blocks);
}

SegInfo A_tree[N_MAX * 4 + 2];
SegInfo B_tree[N_MAX * 4 + 2];

void update (int i, ll a) {
    update_Fen(i, a - A[i]);
    update_tree(max_tree, i, -(a - A[i]));
    update_tree(A_tree, i, -a - (-A[i]));
    if (i + 1 <= N) {
        update_tree(A_tree, i + 1, N, a - A[i]);
    }
    update_tree(B_tree, i, -a - (-A[i]));
    if (1 <= i - 1) {
        update_tree(B_tree, 1, i - 1, a - A[i]);
    }
    A[i] = a;
    del_blocks(i);
    add_blocks(i);
    if (i - 1 >= 1) {
        del_blocks(i - 1);
        add_blocks(i - 1);
    }
    if (i + 1 <= N) {
        del_blocks(i + 1);
        add_blocks(i + 1);
    }
}
int query (int l, int r) {
    l = max(l, query_last(A_tree, r, query_Fen(1, l - 1) - 1));
    r = min(r, query_first(B_tree, l, query_Fen(r + 1, N) - 1));
    return query_cnt(min_tree, l, r);
}

int Q;

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N;
    build_tree(min_tree);
    build_tree(max_tree);
    for (int i = 1; i <= N; i++) {
        ll a; cin >> a;
        update(i, a);
    }
    cin >> Q;
    while (Q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int i; ll a; cin >> i >> a;
            update(i, a);
        } else {
            int l, r;
            cin >> l >> r;
            cout << query(l, r) << "\n";
        }
    }

    return 0;
}

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