Submission #691582

#	Time	Username	Problem	Language	Result	Execution time	Memory
691582		andrei_iorgulescu	Simple (info1cup19_simple)	C++14	30 / 100	285 ms	41676 KiB

subway

#include <bits/stdc++.h>

using namespace std;

#define int long long

int n,a[200005],q;
int inf = 1000000000000000000ll;

struct aint_nod
{
    int lazy = 0,maxpar = -inf,maximp = -inf,minpar = inf,minimp = inf;
};

aint_nod aint[800005];

void build(int p,int l,int r)
{
    if (l == r)
    {
        if (a[l] % 2 == 1)
            aint[p].maximp = a[l],aint[p].minimp = a[l];
        else
            aint[p].maxpar = a[l],aint[p].minpar = a[l];
    }
    else
    {
        int mij = (l + r) / 2;
        int fs = 2 * p,fd = 2 * p + 1;
        build(fs,l,mij);
        build(fd,mij + 1,r);
        aint[p].maxpar = max(aint[fs].maxpar,aint[fd].maxpar);
        aint[p].maximp = max(aint[fs].maximp,aint[fd].maximp);
        aint[p].minpar = min(aint[fs].minpar,aint[fd].minpar);
        aint[p].minimp = min(aint[fs].minimp,aint[fd].minimp);

    }
}

void prop_lazy(int p,int l,int r)
{
    if (aint[p].lazy % 2 == 0)
    {
        aint[p].maxpar += aint[p].lazy;
        aint[p].maximp += aint[p].lazy;
        aint[p].minpar += aint[p].lazy;
        aint[p].minimp += aint[p].lazy;
    }
    else
    {
        swap(aint[p].maxpar,aint[p].maximp);
        swap(aint[p].minpar,aint[p].minimp);
        aint[p].maxpar += aint[p].lazy;
        aint[p].maximp += aint[p].lazy;
        aint[p].minpar += aint[p].lazy;
        aint[p].minimp += aint[p].lazy;
    }
    if (l != r)
    {
        int fs = 2 * p,fd = 2 * p + 1;
        aint[fs].lazy += aint[p].lazy;
        aint[fd].lazy += aint[p].lazy;
    }
    aint[p].lazy = 0;
}

void update(int p,int l,int r,int st,int dr,int val)
{
    prop_lazy(p,l,r);
    if (st <= l and r <= dr)
    {
        aint[p].lazy += val;
        prop_lazy(p,l,r);
        return;
    }
    int fs = 2 * p,fd = 2 * p + 1,mij = (l + r) / 2;
    if (mij >= st)
        update(fs,l,mij,st,dr,val);
    if (mij + 1 <= dr)
        update(fd,mij + 1,r,st,dr,val);
    aint[p].maxpar = max(aint[fs].maxpar,aint[fd].maxpar);
    aint[p].maximp = max(aint[fs].maximp,aint[fd].maximp);
    aint[p].minpar = min(aint[fs].minpar,aint[fd].minpar);
    aint[p].minimp = min(aint[fs].minimp,aint[fd].minimp);
}

pair<int,int>better(pair<int,int>p1,pair<int,int>p2)
{
    if (p1.first == -1 and p1.second == -1)
        return p2;
    if (p2.first == -1 and p2.second == -1)
        return p1;
    pair<int,int>ans;
    ans.first = min(p1.first,p2.first);
    ans.second = max(p1.second,p2.second);
    return ans;
}

pair<int,int>query(int p,int l,int r,int st,int dr)
{
    prop_lazy(p,l,r);
    if (st <= l and r <= dr)
        return {aint[p].minpar,aint[p].maximp};
    int fs = 2 * p,fd = 2 * p + 1,mij = (l + r) / 2;
    pair<int,int>p1 = {-1,-1},p2 = {-1,-1};
    if (mij >= st)
        p1 = query(fs,l,mij,st,dr);
    if (mij + 1 <= dr)
        p2 = query(fd,mij + 1,r,st,dr);
    return better(p1,p2);
}

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,val;
            cin >> x >> y >> val;
            update(1,1,n,x,y,val);
        }
        else
        {
            int x,y;
            cin >> x >> y;
            pair<int,int>qr = query(1,1,n,x,y);
            if (qr.second >= inf / 10 or qr.second <= -inf / 10)
                qr.second = -1;
            if (qr.first <= -inf / 10 or qr.first >= inf / 10)
                qr.first = -1;
            cout << qr.first << ' ' << qr.second << '\n';
        }
    }
    return 0;
}

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