#include #define all(v) v.begin(), v.end() #define prs(v) sort(all(v)); v.erase(unique(all(v)), v.end()) using namespace std; using ll = long long; using P = array; const int tN = 1 << 19; template struct SegTree{ vectorT; merge M; node non; SegTree(const node& non) : non(non), T(tN << 1, non) {} void Set(int i,const node &v){ T[i += tN - 1] = v; } void Init(){ for(int s = tN - 1; s; s--)T[s] = M(T[s << 1], T[s << 1 | 1]); } void Update(int i,const node &v){ T[--i |= tN] = v; while(i >>= 1)T[i] = M(T[i << 1], T[i << 1 | 1]); } node Query(int l,int r) { node L = non, R = non; for(--l |= tN, --r |= tN; l <= r; l >>= 1, r >>= 1){ if(l & 1)L = M(L, T[l++]); if(~r & 1)R = M(T[r--], R); } return M(L, R); } }; struct node { ll l, r, m, a, op; node (ll l,ll r,ll m,ll a) : l(l), r(r), m(m), a(a), op(1) {} node (ll v) : node(v, v, v, v) {} node () : node(0ll) { op = 0; } }; struct M { node operator () (const node &a,const node &b) { if (!a.op) return b; if (!b.op) return a; ll l = min(a.l, a.a + b.l), r = min(b.r, b.a + a.r); ll m = min({a.m, b.m, a.r + b.l}); return node(l, r, m, a.a + b.a); } }; int main(){ cin.tie(0)->sync_with_stdio(0); int n, q; cin >> n >> q; vector A(n + 1); for (int s = 1; s <= n; s++) cin >> A[s]; node non; SegTree T(non); for (int s = 1; s <= n; s++) T.Update(s, A[s]); while (q--) { int op; cin >> op; if (op == 1) { ll l, r, x; cin >> l >> r >> x; ll hp = x, lo = (x + 9) / 10; if (l > 1) { auto le = T.Query(1, l - 1); if (-le.m >= x) { cout << "0\n"; continue; } hp = x + min(0ll, le.r); } T.Update(l, A[l] + hp - x); auto mid = T.Query(l, r); T.Update(l, A[l]); if (-mid.m >= x - lo) hp = lo; else hp = x + min(0ll, mid.r); if (r >= n) { cout << hp << "\n"; continue; } T.Update(r + 1, A[r + 1] + hp - x); auto ri = T.Query(r + 1, n); T.Update(r + 1, A[r + 1]); if (-ri.m >= x) cout << "0\n"; else cout << x + min(0ll, ri.r) << "\n"; } else { ll i, x; cin >> i >> x; A[i] = x; T.Update(i, x); } }; }

제출 #172956

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: