Submission #962347

#TimeUsernameProblemLanguageResultExecution timeMemory
962347alextodoranFish 2 (JOI22_fish2)C++17
5 / 100
4093 ms34576 KiB
/** _ _ __ _ _ _ _ _ _ |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 (l == r) { return (seg_tree[node].val <= val ? l : 0); } 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 (l == r) { return (seg_tree[node].val <= val ? l : N + 1); } 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); ls.push_back(j + 1); } j = i; sum = 0; while (j < N) { sum += A[j]; j = query_first(max_tree, j + 1, -sum); 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...