Submission #1218800

#TimeUsernameProblemLanguageResultExecution timeMemory
1218800countlessProgression (NOI20_progression)C++20
0 / 100
225 ms41292 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; const int INF = 1e9; struct segtree { struct data { int p, s; int pref, suff, best; bool full; data(bool full = false, int pref = -BAD, int suff = -BAD, int best = -BAD, int p = -INF, int s = -INF) : full(full), pref(pref), suff(suff), best(best), p(p), s(s) {;;} }; int l, r; data d; segtree *left, *right; inline data combine(const data &a, const data &b) { if (a.p == -INF) return b; if (b.p == -INF) return a; return data({ a.full and b.full, (a.full and a.p == b.p ? a.pref + b.pref : a.pref), (b.full and a.s == b.s ? a.suff + b.suff : b.suff), max({a.best, b.best, (a.s == b.p ? a.suff + b.pref : 0)}), a.p, b.s }); } 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(true, 1, 1, 1, a[l], a[l]); 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; vector<int> a(n), d1; for (int i = 0; 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; }; // create diff array d1 = derive(a); // build segtree segtree st(0, n-1, d1); // answer queries int type, l, r, s, c; while (q--) { cin >> type; if (type == 1) { cin >> l >> r >> s >> c; l--, r--; assert(0); } else if (type == 2) { cin >> l >> r >> s >> c; l--, r--; assert(0); } else if (type == 3) { cin >> l >> r; l--, r--; int sz = (r - l + 1); cout << min(sz, max(0, st.query(l+1, r).best + 1)) << 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...