Submission #670311

#TimeUsernameProblemLanguageResultExecution timeMemory
670311sandupetrascoSimple (info1cup19_simple)C++14
100 / 100
669 ms30932 KiB
#include <bits/stdc++.h> #define N 200008 typedef long long ll; using namespace std; ifstream fin("test.in"); ofstream fout("test.out"); const long long inf = 1LL * 1e18; int n; struct paritate { ll mx; ll mn; } nul; struct arbore { paritate p; paritate i; } aib[4 * N]; ll Lazy[4 * N]; void Initializare( int i, int x, int st, int dr, int nod ) { if( st == dr ) { if( x % 2 ) aib[nod].i = {x, x}, aib[nod].p = nul; else aib[nod].p = {x, x}, aib[nod].i = nul; } else { int mid = (st + dr) / 2; if( i <= mid ) Initializare( i, x, st, mid, nod << 1 ); else Initializare( i, x, mid + 1, dr, nod << 1|1 ); aib[nod].i.mx = max( aib[nod << 1].i.mx, aib[nod << 1|1].i.mx ); aib[nod].i.mn = min( aib[nod << 1].i.mn, aib[nod << 1|1].i.mn ); aib[nod].p.mx = max( aib[nod << 1].p.mx, aib[nod << 1|1].p.mx ); aib[nod].p.mn = min( aib[nod << 1].p.mn, aib[nod << 1|1].p.mn ); } } void Citire() { int i, x; cin >> n; for( i=1; i<=n; i++ ) cin >> x, Initializare( i, x, 1, n, 1 ); } void ModificAIB( arbore &aib, ll x ) { if( !(x % 2) ) { if( aib.p.mx != -1 && aib.p.mn != inf ) aib.p.mn += x, aib.p.mx += x; if( aib.i.mx != -1 && aib.i.mn != inf ) aib.i.mn += x, aib.i.mx += x; } else { paritate impar = aib.i; if( aib.p.mx == -1 && aib.p.mn == inf ) aib.i = nul; else aib.i.mn = aib.p.mn + x, aib.i.mx = aib.p.mx + x; if( impar.mx == -1 && impar.mn == inf ) aib.p = nul; else aib.p.mn = impar.mn + x, aib.p.mx = impar.mx + x; } } void Update( int i, int j, int x, int st, int dr, int nod ) { if( Lazy[nod] ) { ModificAIB( aib[nod], Lazy[nod] ); if( st != dr ) { Lazy[nod << 1] += Lazy[nod]; Lazy[nod << 1|1] += Lazy[nod]; } Lazy[nod] = 0; } if( st > dr || i > j || st > j || i > dr ) return; if( st >= i && j >= dr ) { ModificAIB( aib[nod], x ); if( st != dr ) { Lazy[nod << 1] += x; Lazy[nod << 1|1] += x; } return; } int mid = ( st + dr ) / 2; Update( i, j ,x, st, mid, nod << 1 ); Update( i, j, x, mid + 1, dr, nod << 1|1 ); aib[nod].i.mx = max( aib[nod << 1].i.mx, aib[nod << 1|1].i.mx ); aib[nod].i.mn = min( aib[nod << 1].i.mn, aib[nod << 1|1].i.mn ); aib[nod].p.mx = max( aib[nod << 1].p.mx, aib[nod << 1|1].p.mx ); aib[nod].p.mn = min( aib[nod << 1].p.mn, aib[nod << 1|1].p.mn ); } arbore Query( int i, int j, int st, int dr, int nod ) { if( Lazy[nod] ) { ModificAIB( aib[nod], Lazy[nod] ); if( st != dr ) { Lazy[nod << 1] += Lazy[nod]; Lazy[nod << 1|1] += Lazy[nod]; } Lazy[nod] = 0; } if( st > dr || i > j || st > j || i > dr ) return { nul, nul }; if( st >= i && j >= dr ) return aib[nod]; int mid = (st + dr) / 2; arbore a = {nul, nul}, b = {nul, nul}; if( i <= mid ) a = Query( i, j, st, mid, nod << 1 ); if( j > mid ) b = Query( i, j, mid + 1, dr, nod << 1|1 ); arbore nou; nou.i.mx = max( a.i.mx, b.i.mx ); nou.i.mn = min( a.i.mn, b.i.mn ); nou.p.mx = max( a.p.mx, b.p.mx ); nou.p.mn = min( a.p.mn, b.p.mn ); return nou; } void Rezolvare() { int i; int q; int a, b; int val; int task; cin >> q; while( q-- ) { cin >> task; if( task == 0 ) { cin >> a >> b >> val; Update( a, b, val, 1, n, 1 ); } else { cin >> a >> b; arbore nr = Query( a, b, 1, n, 1 ); cout << ((nr.p.mn == inf) ? -1 : nr.p.mn) << " "; cout << nr.i.mx; cout << "\n"; } } } int main() { nul = { -1, inf }; Citire(); Rezolvare(); return 0; }

Compilation message (stderr)

subway.cpp: In function 'void Rezolvare()':
subway.cpp:162:9: warning: unused variable 'i' [-Wunused-variable]
  162 |     int i;
      |         ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...