Submission #1218786

#TimeUsernameProblemLanguageResultExecution timeMemory
1218786countlessProgression (NOI20_progression)C++20
35 / 100
261 ms33580 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; #define sp <<" "<< #define endl "\n" const int BAD = 0; struct segtree { struct data { int pref, suff, best; bool full; data(bool full = false, int pref = -BAD, int suff = -BAD, int best = -BAD) : full(full), 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.full and b.full, (a.full ? a.pref + b.pref : a.pref), (b.full ? a.suff + b.suff : b.suff), 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) { d = data((a[l] == 0), (a[l] == 0), (a[l] == 0), (a[l] == 0)); 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); cout << min(sz, max(0, st.query(l+2, r).best + 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...