oj.uz

Submission #908205

# Submission time Handle Problem Language Result Execution time Memory
908205 2024-01-16T09:32:19 Z andrei_iorgulescu Simple (info1cup19_simple) C++14
100 / 100
 416 ms 43336 KB 
#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[2 * nod].lazy += aint[nod].lazy;
        aint[2 * nod + 1].lazy += aint[nod].lazy;
        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;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31832 KB Output is correct
2 Correct 11 ms 31836 KB Output is correct
3 Correct 13 ms 31860 KB Output is correct
4 Correct 12 ms 31832 KB Output is correct
5 Correct 12 ms 31836 KB Output is correct
6 Correct 12 ms 31948 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 36436 KB Output is correct
2 Correct 313 ms 41836 KB Output is correct
3 Correct 340 ms 41808 KB Output is correct
4 Correct 331 ms 41756 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31832 KB Output is correct
2 Correct 11 ms 31836 KB Output is correct
3 Correct 13 ms 31860 KB Output is correct
4 Correct 12 ms 31832 KB Output is correct
5 Correct 12 ms 31836 KB Output is correct
6 Correct 12 ms 31948 KB Output is correct
7 Correct 145 ms 36436 KB Output is correct
8 Correct 313 ms 41836 KB Output is correct
9 Correct 340 ms 41808 KB Output is correct
10 Correct 331 ms 41756 KB Output is correct
11 Correct 140 ms 37200 KB Output is correct
12 Correct 346 ms 42228 KB Output is correct
13 Correct 403 ms 42976 KB Output is correct
14 Correct 416 ms 42052 KB Output is correct
15 Correct 395 ms 43336 KB Output is correct
16 Correct 82 ms 39636 KB Output is correct