Submission #1218768

#TimeUsernameProblemLanguageResultExecution timeMemory
1218768countlessProgression (NOI20_progression)C++20
0 / 100
196 ms33236 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; #define sp <<" "<< #define endl "\n" struct segtree { int l, r; int zero; segtree *left, *right; void merge() { zero = left->zero + right->zero; } segtree(int l, int r, vector<int> &a) : l(l), r(r) { if (l == r) { zero = (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(); } int query(int ql, int qr) { if (ql > r or qr < l) return 0; if (ql <= l and r <= qr) return zero; return 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, st.query(l+2, r) + 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...