Submission #1016910

#TimeUsernameProblemLanguageResultExecution timeMemory
1016910MilosMilutinovicProgression (NOI20_progression)C++14
0 / 100
312 ms134668 KiB
#include <bits/stdc++.h> using namespace std; const int MAX = 300300; const long long inf = (long long) 1e18; struct Value { struct Node { long long sum; long long coeff; }; int n; Node st[8 * MAX]; void Modify(int id, int l, int r, int ll, int rr, long long x, long long y) { if (ll <= l && r <= rr) { st[id].sum += x; st[id].coeff += y; return; } int mid = (l + r) >> 1; if (rr <= mid) { Modify(id * 2, l, mid, ll, rr, x, y); } else if (ll > mid) { Modify(id * 2 + 1, mid + 1, r, ll, rr, x, y); } else { Modify(id * 2, l, mid, ll, rr, x, y); Modify(id * 2 + 1, mid + 1, r, ll, rr, x, y); } } Node Query(int id, int l, int r, int p) { if (l == r) { return st[id]; } int mid = (l + r) >> 1; Node nd; if (p <= mid) { nd = Query(id * 2, l, mid, p); } else { nd = Query(id * 2 + 1, mid + 1, r, p); } return {st[id].sum + nd.sum, st[id].coeff + nd.coeff}; } long long Get(int i) { Node nd = Query(1, 0, n - 1, i); return nd.sum + nd.coeff * i; } } val; struct Solver { struct Node { int len; int mx; int mx_l; int mx_r; long long val_l; long long val_r; long long lzy_add; long long lzy_set; Node() { lzy_set = inf; lzy_add = 0; } }; Node Merge(Node a, Node b) { Node nd; nd.len = a.len + b.len; nd.mx = max(a.mx, b.mx); nd.mx_l = a.mx_l; nd.mx_r = b.mx_r; if (a.val_r == b.val_l) { nd.mx = max(nd.mx, a.mx_l + b.mx_r); if (a.mx_l == a.len) { nd.mx_l = max(nd.mx_l, a.len + b.mx_l); } if (b.mx_r == b.len) { nd.mx_r = max(nd.mx_r, a.mx_r + b.len); } } nd.val_l = a.val_l; nd.val_r = b.val_r; return nd; } Node st[8 * MAX]; void Push(int id) { if (st[id].lzy_set == inf) { st[id * 2].val_l += st[id].lzy_add; st[id * 2].val_r += st[id].lzy_add; st[id * 2 + 1].val_l += st[id].lzy_add; st[id * 2 + 1].val_r += st[id].lzy_add; st[id * 2].lzy_add += st[id].lzy_add; st[id * 2 + 1].lzy_add += st[id].lzy_add; st[id].lzy_add = 0; } else { st[id * 2].val_l = st[id].lzy_set + st[id].lzy_add; st[id * 2].val_r = st[id].lzy_set + st[id].lzy_add; st[id * 2 + 1].val_l = st[id].lzy_set + st[id].lzy_add; st[id * 2 + 1].val_r = st[id].lzy_set + st[id].lzy_add; st[id * 2].lzy_set = st[id].lzy_set; st[id * 2].lzy_add = st[id].lzy_add; st[id * 2 + 1].lzy_set = st[id].lzy_set; st[id * 2 + 1].lzy_add = st[id].lzy_add; st[id * 2].mx = st[id * 2].mx_l = st[id * 2].mx_r = st[id * 2].len; st[id * 2 + 1].mx = st[id * 2 + 1].mx_l = st[id * 2 + 1].mx_r = st[id * 2 + 1].len; st[id].lzy_set = inf; st[id].lzy_add = 0; } } void Build(int id, int l, int r) { if (l == r) { st[id].val_l = st[id].val_r = 0; st[id].len = 1; st[id].mx = st[id].mx_l = st[id].mx_r = 1; return; } int mid = (l + r) >> 1; Build(id * 2, l, mid); Build(id * 2 + 1, mid + 1, r); st[id] = Merge(st[id * 2], st[id * 2 + 1]); } void Set(int id, int l, int r, int ll, int rr, long long x) { if (ll <= l && r <= rr) { st[id].mx = st[id].mx_l = st[id].mx_r = st[id].len; st[id].val_l = x; st[id].val_r = x; st[id].lzy_set = x; st[id].lzy_add = 0; Push(id); return; } int mid = (l + r) >> 1; if (rr <= mid) { Set(id * 2, l, mid, ll, rr, x); } else if (ll > mid) { Set(id * 2 + 1, mid + 1, r, ll, rr, x); } else { Set(id * 2, l, mid, ll, rr, x); Set(id * 2 + 1, mid + 1, r, ll, rr, x); } st[id] = Merge(st[id * 2], st[id * 2 + 1]); } void Add(int id, int l, int r, int ll, int rr, long long x) { if (ll <= l && r <= rr) { st[id].lzy_add += x; Push(id); return; } int mid = (l + r) >> 1; if (rr <= mid) { Add(id * 2, l, mid, ll, rr, x); } else if (ll > mid) { Add(id * 2 + 1, mid + 1, r, ll, rr, x); } else { Add(id * 2, l, mid, ll, rr, x); Add(id * 2 + 1, mid + 1, r, ll, rr, x); } st[id] = Merge(st[id * 2], st[id * 2 + 1]); } Node Query(int id, int l, int r, int ll, int rr) { if (ll <= l && r <= rr) { return st[id]; } Push(id); int mid = (l + r) >> 1; Node ret; if (rr <= mid) { ret = Query(id * 2, l, mid, ll, rr); } else if (ll > mid) { ret = Query(id * 2 + 1, mid + 1, r, ll, rr); } else { ret = Merge(Query(id * 2, l, mid, ll, rr), Query(id * 2 + 1, mid + 1, r, ll, rr)); } st[id] = Merge(st[id * 2], st[id * 2 + 1]); return ret; } } st; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, q; cin >> n >> q; for (int i = 0; i < n; i++) { int d; cin >> d; val.Modify(1, 0, n - 1, i, i, d, 0); } val.n = n; st.Build(1, 0, n - 1); for (int i = 0; i + 1 < n; i++) { st.Set(1, 0, n - 1, i, i, val.Get(i) - val.Get(i + 1)); } while (q--) { int op; cin >> op; if (op == 1) { } if (op == 2) { } if (op == 3) { int l, r; cin >> l >> r; --l; --r; if (l == r) { cout << 1 << '\n'; } else { cout << st.Query(1, 0, n - 1, l, r - 1).mx + 1 << '\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...