Submission #907579

#TimeUsernameProblemLanguageResultExecution timeMemory
907579andrei_iorgulescuSimple (info1cup19_simple)C++14
30 / 100
297 ms42064 KiB
#include <bits/stdc++.h> using namespace std; #define int long long int inf = 1e18; int inf2 = 1e17; struct aint_node { int lazy = 0,maxpar = -inf,minpar = inf,maximp = -inf,minimp = inf; }; aint_node cel_mai_nebazat; int n,q,a[200005]; aint_node aint[800005]; aint_node combina(aint_node l,aint_node r) { aint_node rez; rez.lazy = 0; rez.maxpar = max(l.maxpar,r.maxpar); rez.maximp = max(l.maximp,r.maximp); rez.minpar = min(l.minpar,r.minpar); rez.minimp = min(l.minimp,r.minimp); return rez; } void build(int nod,int l,int r) { aint[nod].lazy = 0; if (l == r) { if (a[l] % 2 == 0) { aint[nod].maxpar = aint[nod].minpar = a[l]; aint[nod].maximp = -inf; aint[nod].minimp = inf; } else { aint[nod].maximp = aint[nod].minimp = a[l]; aint[nod].maxpar = -inf; aint[nod].minpar = inf; } } else { int mij = (l + r) / 2; build(2 * nod,l,mij); build(2 * nod + 1,mij + 1,r); aint[nod] = combina(aint[2 * nod],aint[2 * nod + 1]); } } void propaga(int nod,int l,int r) { if (l == r) aint[nod].lazy = 0; else { aint[2 * nod].maxpar += aint[nod].lazy; aint[2 * nod].minpar += aint[nod].lazy; aint[2 * nod].maximp += aint[nod].lazy; aint[2 * nod].minimp += aint[nod].lazy; if (aint[nod].lazy % 2 == 1) { swap(aint[2 * nod].maxpar,aint[2 * nod].maximp); swap(aint[2 * nod].minpar,aint[2 * nod].minimp); } aint[2 * nod + 1].maxpar += aint[nod].lazy; aint[2 * nod + 1].minpar += aint[nod].lazy; aint[2 * nod + 1].maximp += aint[nod].lazy; aint[2 * nod + 1].minimp += aint[nod].lazy; if (aint[nod].lazy % 2 == 1) { swap(aint[2 * nod + 1].maxpar,aint[2 * nod + 1].maximp); swap(aint[2 * nod + 1].minpar,aint[2 * nod + 1].minimp); } aint[nod].lazy = 0; } } void update(int nod,int l,int r,int st,int dr,int val) { propaga(nod,l,r); if (r < st or dr < l) return; if (st <= l and r <= dr) { aint[nod].lazy += val; aint[nod].maxpar += val; aint[nod].minpar += val; aint[nod].maximp += val; aint[nod].minimp += val; if (val % 2 == 1) { swap(aint[nod].maxpar,aint[nod].maximp); swap(aint[nod].minpar,aint[nod].minimp); } return; } int mij = (l + r) / 2; update(2 * nod,l,mij,st,dr,val); update(2 * nod + 1,mij + 1,r,st,dr,val); aint[nod] = combina(aint[2 * nod],aint[2 * nod + 1]); } aint_node query(int nod,int l,int r,int st,int dr) { propaga(nod,l,r); if (r < st or dr < l) return cel_mai_nebazat; if (st <= l and r <= dr) return aint[nod]; int mij = (l + r) / 2; return combina(query(2 * nod,l,mij,st,dr),query(2 * nod + 1,mij + 1,r,st,dr)); } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; build(1,1,n); cin >> q; for (int i = 1; i <= q; i++) { int tip; cin >> tip; if (tip == 0) { int x,y,z; cin >> x >> y >> z; update(1,1,n,x,y,z); } else { int x,y; cin >> x >> y; aint_node rsp = query(1,1,n,x,y); if (rsp.minpar >= inf2) cout << -1 << ' '; else cout << rsp.minpar << ' '; if (rsp.maximp <= -inf2) cout << -1 << '\n'; else cout << rsp.maximp << '\n'; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...