oj.uz

Submission #670311

# Submission time Handle Problem Language Result Execution time Memory
670311 2022-12-08T16:55:33 Z sandupetrasco Simple (info1cup19_simple) C++14
100 / 100
 669 ms 30932 KB 
#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

subway.cpp: In function 'void Rezolvare()':
subway.cpp:162:9: warning: unused variable 'i' [-Wunused-variable]
  162 |     int i;
      |         ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 724 KB Output is correct
2 Correct 11 ms 784 KB Output is correct
3 Correct 13 ms 1124 KB Output is correct
4 Correct 14 ms 1172 KB Output is correct
5 Correct 14 ms 1092 KB Output is correct
6 Correct 14 ms 1152 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 12540 KB Output is correct
2 Correct 648 ms 25164 KB Output is correct
3 Correct 643 ms 25276 KB Output is correct
4 Correct 669 ms 25248 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 724 KB Output is correct
2 Correct 11 ms 784 KB Output is correct
3 Correct 13 ms 1124 KB Output is correct
4 Correct 14 ms 1172 KB Output is correct
5 Correct 14 ms 1092 KB Output is correct
6 Correct 14 ms 1152 KB Output is correct
7 Correct 309 ms 12540 KB Output is correct
8 Correct 648 ms 25164 KB Output is correct
9 Correct 643 ms 25276 KB Output is correct
10 Correct 669 ms 25248 KB Output is correct
11 Correct 318 ms 15268 KB Output is correct
12 Correct 653 ms 29672 KB Output is correct
13 Correct 651 ms 30456 KB Output is correct
14 Correct 644 ms 29684 KB Output is correct
15 Correct 654 ms 30932 KB Output is correct
16 Correct 296 ms 23056 KB Output is correct