Submission #1061509

#TimeUsernameProblemLanguageResultExecution timeMemory
1061509PanosPaskSjeckanje (COCI21_sjeckanje)C++14
0 / 110
1 ms344 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll INF = 1e18; struct SegTree { struct Node { // segments[0]: The minimum and maximum of the leftmost segment in the Nod // segments[1]: The minimum and maximum of the rightmost segment in the Node ll segments[2][2] = {{0, 0}, {0, 0}}; // Is the whole segment unitied bool unite = true; bool is_def = false; ll ans = 0; ll calc_segment(int i) { return segments[i][1] - segments[i][0]; } Node(void) { for (int i = 0; i < 2; i++) { for (int j = 0; j < 2; j++) { segments[i][j] = 0; } } ans = 0; unite = true; is_def = false; } }; void update(Node& a, int x) { for (int i = 0; i < 2; i++) { for (int j = 0; j < 2; j++) { a.segments[i][j] += x; } } } Node solo(int v) { Node res; update(res, v); return res; } Node merge(Node& a, Node& b) { Node res; if (b.is_def) { res = a; res.unite = false; return res; } ll ans = a.ans + b.ans; res.segments[0][0] = a.segments[0][0]; res.segments[0][1] = a.segments[0][1]; res.segments[1][0] = b.segments[1][0]; res.segments[1][1] = b.segments[1][1]; if (max(a.segments[1][0], b.segments[0][0]) > min(a.segments[1][1], b.segments[1][1])) { // Merge the 2 things ll mx = max(a.segments[1][1], b.segments[0][1]); ll mn = min(a.segments[1][0], b.segments[0][0]); ans += mx - mn - a.calc_segment(1) - b.calc_segment(0); if (a.unite) { res.segments[0][0] = mn; res.segments[0][1] = mx; } if (b.unite) { res.segments[1][0] = mn; res.segments[1][1] = mx; } if (a.unite && b.unite) { res.unite; } } res.ans = ans; return res; } Node DEFAULT; const int NO_OP = 0; int size; vector<Node> tree; vector<int> op; void init(int N) { size = 1; while (size < N) { size *= 2; } DEFAULT.is_def = true; tree.assign(2 * size, DEFAULT); op.assign(2 * size, NO_OP); } void propagate(int x) { update(tree[2 * x + 1], op[x]); update(tree[2 * x + 2], op[x]); op[2 * x + 1] += op[x]; op[2 * x + 2] += op[x]; op[x] = NO_OP; } void add(int l, int r, int v, int x, int lx, int rx) { if (lx >= r || l >= rx) { return; } else if (l <= lx && rx <= r) { update(tree[x], v); tree[x].is_def = false; op[x] += v; return; } propagate(x); int mid = (lx + rx) / 2; add(l, r, v, 2 * x + 1, lx, mid); add(l, r, v, 2 * x + 2, mid, rx); tree[x] = merge(tree[2 * x + 1], tree[2 * x + 2]); } void add(int l, int r, int v) { add(l, r, v, 0, 0, size); } Node calc(int l, int r, int x, int lx, int rx) { if (l >= rx || lx >= r) { return DEFAULT; } else if (l <= lx && rx <= r) { return tree[x]; } int mid = (lx + rx) / 2; Node n1 = calc(l, r, 2 * x + 1, lx, mid); Node n2 = calc(l, r, 2 * x + 2, mid, rx); return merge(n1, n2); } ll calc(int l, int r) { return calc(l, r, 0, 0, size).ans; } }; int N, Q; SegTree st; int main(void) { scanf("%d %d", &N, &Q); st.init(N); for (int i = 0; i < N; i++) { int v; scanf("%d", &v); st.add(i, i + 1, v); } while (Q--) { int l, r, x; scanf("%d %d %d", &l, &r, &x); l--; st.add(l, r, x); printf("%lld\n", st.calc(0, N)); } return 0; }

Compilation message (stderr)

Main.cpp: In member function 'SegTree::Node SegTree::merge(SegTree::Node&, SegTree::Node&)':
Main.cpp:86:21: warning: statement has no effect [-Wunused-value]
   86 |                 res.unite;
      |                 ~~~~^~~~~
Main.cpp: In function 'int main()':
Main.cpp:171:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  171 |     scanf("%d %d", &N, &Q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:177:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  177 |         scanf("%d", &v);
      |         ~~~~~^~~~~~~~~~
Main.cpp:183:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  183 |         scanf("%d %d %d", &l, &r, &x);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...