Submission #1240891

#TimeUsernameProblemLanguageResultExecution timeMemory
1240891trufanov.pProgression (NOI20_progression)C++20
0 / 100
835 ms109344 KiB
#include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cctype> #include <string> #include <queue> #include <unordered_set> #include <deque> #include <numeric> #include <cmath> #include <unordered_map> #include <set> using namespace std; #pragma GCC optimize("O3") #pragma GCC optimization("Ofast,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") typedef long long ll; struct Node { int maxseg; // ll maxsegval; // int maxpref; // ll first; // int maxsuff; // ll last; // ll addval; // ll setval; // bool hasset; // int len; // bool neutral; // ll summ; Node() :addval(0), setval(0), hasset(false), len(0), neutral(false), summ(0) {} Node(bool _) :neutral(true) {} Node(ll x) { maxseg = 1; maxsegval = x; maxpref = 1; first = x; maxsuff = 1; last = x; addval = 0; setval = 0; hasset = false; len = 1; neutral = false; summ = 0; } }; void push(int v, vector<Node>& t) { if (!t[v].hasset) { t[2 * v + 1].addval += t[v].addval; t[2 * v + 2].addval += t[v].addval; t[v].addval = 0; } else { t[2 * v + 1].setval = t[v].setval; t[2 * v + 1].addval = t[v].addval; t[2 * v + 1].hasset = true; t[2 * v + 2].setval = t[v].setval; t[2 * v + 2].addval = t[v].addval; t[2 * v + 2].hasset = true; t[v].setval = 0; t[v].addval = 0; t[v].hasset = false; } } Node selfpush(const Node& a) { Node b = a; if (!a.hasset) { b.first += b.addval; b.last += b.addval; b.maxsegval += b.addval; b.summ += b.addval * b.len; b.addval = 0; } else { b.first = b.setval + b.addval; b.last = b.setval + b.addval; b.maxsegval = b.setval + b.addval; b.maxpref = b.len; b.maxsuff = b.len; b.maxseg = b.len; b.summ = (b.setval + b.addval) * b.len; b.hasset = 0; b.setval = 0; b.addval = 0; } return b; } Node unite(const Node& a_, const Node& b_) { Node a = selfpush(a_), b = selfpush(b_); if (a_.neutral) { return b; } else if (b_.neutral) { return a; } Node c; c.neutral = false; c.len = a.len + b.len; c.summ = a.summ + b.summ; /*ll afirstreal = (a.hasset ? a.setval + a.addval : a.first + a.addval); ll alastreal = (a.hasset ? a.setval + a.addval : a.last + a.addval); ll bfirstreal = (b.hasset ? b.setval + b.addval : b.first + b.addval); ll blastreal = (b.hasset ? b.setval + b.addval : b.last + b.addval); c.first = afirstreal; c.maxpref = a.maxpref + (a.maxpref == a.len && afirstreal == bfirstreal ? b.maxpref : 0); c.last = blastreal; c.maxsuff = b.maxsuff + (b.maxsuff == b.len && blastreal == alastreal ? a.maxsuff : 0); ll amaxreal = (a.hasset ? a.setval + a.addval : a.maxsegval + a.addval); ll bmaxreal = (b.hasset ? b.setval + b.addval : b.maxsegval + b.addval); if (a.maxseg > b.maxseg) { c.maxseg = a.maxseg; c.maxsegval = amaxreal; } else { c.maxseg = b.maxseg; c.maxsegval = bmaxreal; } if (alastreal == bfirstreal && a.maxsuff + b.maxpref > c.maxseg) { c.maxseg = a.maxsuff + b.maxpref; c.maxsegval = alastreal; }*/ c.first = a.first; c.maxpref = a.maxpref + (a.maxpref == a.len && a.first == b.first ? b.maxpref : 0); c.last = b.last; c.maxsuff = b.maxsuff + (b.maxsuff == b.len && b.last == a.last ? a.maxsuff : 0); if (a.maxseg > b.maxseg) { c.maxseg = a.maxseg; c.maxsegval = a.maxsegval; } else { c.maxseg = b.maxseg; c.maxsegval = b.maxsegval; } if (a.last == b.first && a.maxsuff + b.maxpref > c.maxseg) { c.maxseg = a.maxsuff + b.maxpref; c.maxsegval = a.last; } return c; } void build(int v, int l, int r, vector<Node>& t, const vector<ll>& a) { if (l == r - 1) { t[v] = Node(a[l]); return; } int m = (l + r) / 2; build(2 * v + 1, l, m, t, a); build(2 * v + 2, m, r, t, a); t[v] = unite(t[2 * v + 1], t[2 * v + 2]); } Node query(int v, int l, int r, int askl, int askr, vector<Node>& t) { if (l >= askr || r <= askl) { return Node(true); } if (l >= askl && r <= askr) { return selfpush(t[v]); } push(v, t); int m = (l + r) / 2; auto ans_left = query(2 * v + 1, l, m, askl, askr, t); auto ans_right = query(2 * v + 2, m, r, askl, askr, t); t[v] = unite(t[2 * v + 1], t[2 * v + 2]); return unite(ans_left, ans_right); } void range_add(int v, int l, int r, int askl, int askr, ll val, vector<Node>& t) { if (l >= askr || r <= askl) { return; } if (l >= askl && r <= askr) { t[v].addval += val; return; } push(v, t); int m = (l + r) / 2; range_add(2 * v + 1, l, m, askl, askr, val, t); range_add(2 * v + 2, m, r, askl, askr, val, t); t[v] = unite(t[2 * v + 1], t[2 * v + 2]); } void range_set(int v, int l, int r, int askl, int askr, ll val, vector<Node>& t) { if (l >= askr || r <= askl) { return; } if (l >= askl && r <= askr) { t[v].hasset = true; t[v].setval = val; t[v].addval = 0; return; } push(v, t); int m = (l + r) / 2; range_set(2 * v + 1, l, m, askl, askr, val, t); range_set(2 * v + 2, m, r, askl, askr, val, t); t[v] = unite(t[2 * v + 1], t[2 * v + 2]); } ll get_elem(int i, int n, vector<Node>& t) { return query(0, 0, n, i, i + 1, t).maxsegval; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, q; cin >> n >> q; vector<ll> orig(n); for (int i = 0; i < n; ++i) { cin >> orig[i]; } orig.insert(orig.begin(), 1e9); n++; vector<ll> diff(n); diff[0] = orig[0]; for (int i = 1; i < n; ++i) { diff[i] = orig[i] - orig[i - 1]; } vector<Node> t(4 * n); build(0, 0, n, t, diff); for (int _ = 0; _ < q; ++_) { int type; cin >> type; if (type == 1) { int l, r; ll s, c; cin >> l >> r >> s >> c; //l--, r--; range_add(0, 0, n, l, l + 1, s, t); range_add(0, 0, n, l + 1, r + 1, c, t); if (r + 1 < n) { range_add(0, 0, n, r + 1, r + 2, -(s + (r - l) * c), t); } } else if (type == 2) { int l, r; ll s, c; cin >> l >> r >> s >> c; //l--, r--; ll realr = query(0, 0, n, 0, r + 1, t).summ; ll prv = (l == 0 ? 0ll : get_elem(l - 1, n, t)); range_set(0, 0, n, l, l + 1, s - prv, t); range_set(0, 0, n, l + 1, r + 1, c, t); if (r + 1 < n) { ll nxt = get_elem(r + 1, n, t); range_add(0, 0, n, r + 1, r + 2, realr - (s + (r - l) * c), t); } } else { int l, r; cin >> l >> r; //l--, r--; cout << query(0, 0, n, l, r + 1, t).maxseg + 1 << '\n'; } } } /* 10 6 1 2 3 4 1 2 3 4 5 5 3 1 10 1 1 4 -1 -1 3 1 10 3 9 10 2 5 10 -2 -2 3 1 10 */
#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...