Submission #670311

#	Time	Username	Problem	Language	Result	Execution time	Memory
670311		sandupetrasco	Simple (info1cup19_simple)	C++14	100 / 100	669 ms	30932 KiB

subway

#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;
      |         ^

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40