Submission #1218781

#TimeUsernameProblemLanguageResultExecution timeMemory
1218781countlessProgression (NOI20_progression)C++20
0 / 100
210 ms34772 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; #define sp <<" "<< #define endl "\n" const int BAD = 1e9; struct segtree { struct data { int sum, pref, suff, best; data(int sum = -BAD, int pref = -BAD, int suff = -BAD, int best = -BAD) : sum(sum), pref(pref), suff(suff), best(best) {;;} }; int l, r; data d; segtree *left, *right; // this can be made much simpler because we don't have non-negative entries inline data combine(const data &a, const data &b) { return data({ a.sum + b.sum, max(a.pref, a.sum + b.pref), max(a.suff + b.sum, b.pref), max({a.best, b.best, a.suff + b.pref}) }); } inline void merge() { d = combine(left->d, right->d); } segtree(int l, int r, vector<int> &a) : l(l), r(r) { if (l == r) { if (a[l] == 0) d = data(1, 1, 1, 1); else d = data(); left = right = nullptr; return; } int m = (l+r) / 2; left = new segtree(l, m, a); right = new segtree(m+1, r, a); merge(); } data query(int ql, int qr) { if (ql > r or qr < l) return data(); if (ql <= l and r <= qr) return d; return combine(left->query(ql, qr), right->query(ql, qr)); } }; void solve() { int n, q; cin >> n >> q; int sync = 0; n += sync; vector<int> a(n), d1, d2; for (int i = sync; i < n; i++) cin >> a[i]; auto derive = [&](vector<int> &a) -> vector<int> { vector<int> res(n); for (int i = 1; i < n; i++) { res[i] = a[i] - a[i-1]; } return res; }; auto print = [&](vector<int> &a) -> void { for (auto &x : a) { cerr << x << " "; } cerr << endl; }; auto enact = [&]() -> void { d1 = derive(a); d2 = derive(d1); }; auto debug = [&]() -> void { print(a), print(d1), print(d2); cerr << endl; }; enact(); // debug(); segtree st(0, n-1, d2); int type, l, r, s, c; while (q--) { cin >> type; if (type == 1) { cin >> l >> r >> s >> c; l--, r--; l += sync, r += sync; assert(0); } else if (type == 2) { cin >> l >> r >> s >> c; l--, r--; l += sync, r += sync; assert(0); } else if (type == 3) { cin >> l >> r; l--, r--; l += sync, r += sync; int sz = (r - l + 1); if (sz <= 2) { cout << sz << endl; continue; } int que = st.query(l+2, r).best; if (que < 0) que = 0; cout << que + 2 << endl; } } } signed main() { cin.tie(0); ios_base::sync_with_stdio(false); int t = 1; // cin >> t; while (t--) solve(); }
#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...