oj.uz

Submission #907582

# Submission time Handle Problem Language Result Execution time Memory
907582 2024-01-15T21:46:37 Z andrei_iorgulescu Simple (info1cup19_simple) C++14
30 / 100
 1000 ms 32916 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[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);
            for (int j = x; j <= y; j++)
                a[j] += z;
        }
        else
        {
            int x,y;
            cin >> x >> y;
            aint_node rsp = query(1,1,n,x,y);
            pair<int,int>afis;
            if (rsp.minpar >= inf2)
                afis.first = -1;
            else
                afis.first = rsp.minpar;
            if (rsp.maximp <= -inf2)
                afis.second = -1;
            else
                afis.second = rsp.maximp;
            pair<int,int>afisbrut = {inf,-inf};
            for (int j = x; j <= y; j++)
            {
                if (a[j] % 2 == 0)
                    afisbrut.first = min(afisbrut.first,a[j]);
                if (a[j] % 2 == 1)
                    afisbrut.second = max(afisbrut.second,a[j]);
            }
            if (afisbrut.first >= inf2)
                afisbrut.first = -1;
            if (afisbrut.second <= -inf2)
                afisbrut.second = -1;
            cout << afisbrut.first << ' ' << afisbrut.second << '\n';
        }
    }
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31836 KB Output is correct
2 Correct 18 ms 31936 KB Output is correct
3 Correct 23 ms 31980 KB Output is correct
4 Correct 26 ms 31836 KB Output is correct
5 Correct 23 ms 32008 KB Output is correct
6 Correct 26 ms 31836 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1036 ms 32916 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31836 KB Output is correct
2 Correct 18 ms 31936 KB Output is correct
3 Correct 23 ms 31980 KB Output is correct
4 Correct 26 ms 31836 KB Output is correct
5 Correct 23 ms 32008 KB Output is correct
6 Correct 26 ms 31836 KB Output is correct
7 Execution timed out 1036 ms 32916 KB Time limit exceeded
8 Halted 0 ms 0 KB -