제출 #230775

#제출 시각아이디문제언어결과실행 시간메모리
230775andreiomdSimple (info1cup19_simple)C++11
100 / 100
464 ms34552 KiB
#include <iostream> using namespace std; const long long INF = 1LL * 1e18; int N, X, Q, Type, a, b, Val; struct NodeT { long long Min_Even, Max_Even, Min_Odd, Max_Odd; NodeT () { Min_Even = Min_Odd = INF; Max_Even = Max_Odd = -INF; } }; class SegmentTree { static const int NMAX = 2e5 + 5; NodeT A[(NMAX << 2)]; long long Lazy[(NMAX << 2)]; inline void Update_Node (NodeT &X, long long Val) { if(X.Min_Even == INF && X.Min_Odd == INF) { if(Val & 1) X.Min_Odd = X.Max_Odd = Val; else X.Min_Even = X.Max_Even = Val; return; } if(Val & 1) { swap(X.Min_Even, X.Min_Odd); swap(X.Max_Even, X.Max_Odd); } if(X.Min_Even != INF) X.Min_Even += 1LL * Val, X.Max_Even += 1LL * Val; if(X.Min_Odd != INF) X.Min_Odd += 1LL * Val, X.Max_Odd += 1LL * Val; return; } inline void Go (int Node, int a, int b) { if(a == b) return; if(!Lazy[Node]) return; Update_Node(A[2 * Node], Lazy[Node]); Update_Node(A[2 * Node + 1], Lazy[Node]); Lazy[2 * Node] += Lazy[Node]; Lazy[2 * Node + 1] += Lazy[Node]; Lazy[Node] = 0; return; } inline NodeT Merge (NodeT X, NodeT Y) { NodeT ans; ans.Min_Even = min(X.Min_Even, Y.Min_Even); ans.Max_Even = max(X.Max_Even, Y.Max_Even); ans.Min_Odd = min(X.Min_Odd, Y.Min_Odd); ans.Max_Odd = max(X.Max_Odd, Y.Max_Odd); return ans; } public: inline void Update (int Node, int a, int b, int ua, int ub, int Val) { if(ua <= a && b <= ub) { Lazy[Node] += 1LL * Val; Update_Node(A[Node], Val); return; } Go(Node, a, b); int Mid = (a + b) >> 1; if(ua <= Mid) Update(2 * Node, a, Mid, ua, ub, Val); if(ub > Mid) Update(2 * Node + 1, Mid + 1, b, ua, ub, Val); A[Node] = Merge(A[2 * Node], A[2 * Node + 1]); return; } inline NodeT Query (int Node, int a, int b, int qa, int qb) { if(qa <= a && b <= qb) return A[Node]; Go(Node, a, b); int Mid = (a + b) >> 1; NodeT p1, p2; if(qa <= Mid) p1 = Query(2 * Node, a, Mid, qa, qb); if(qb > Mid) p2 = Query(2 * Node + 1, Mid + 1, b, qa, qb); return Merge(p1, p2); } } AINT; static inline void Load () { ios_base :: sync_with_stdio(false); cin.tie(nullptr); cin >> N; for(int i = 1; i <= N; ++i) cin >> X, AINT.Update(1, 1, N, i, i, X); return; } static inline void TestCase () { cin >> Type >> a >> b; if(Type == 0) { cin >> Val; AINT.Update(1, 1, N, a, b, Val); return; } NodeT ans = AINT.Query(1, 1, N, a, b); if(ans.Min_Even == INF) ans.Min_Even = -1; if(ans.Max_Odd == -INF) ans.Max_Odd = -1; printf("%lld %lld\n", 1LL * ans.Min_Even, 1LL * ans.Max_Odd); return; } static inline void Solve () { cin >> Q; while(Q--) TestCase(); return; } int main() { Load(); Solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...