Submission #733679

#	Time	Username	Problem	Language	Result	Execution time	Memory
733679		MateiKing80	Simple (info1cup19_simple)	C++14	100 / 100	427 ms	53096 KiB

subway

#include <iostream>

using namespace std;

long long v[200005];

struct nod
{
    long long maxp=-1,minp=-1,maxi=-1,mini=-1,lazy=0;
} aint[2000005];


nod join(nod a, nod b)
{
    nod x;
    x.lazy=0;
    x.maxp=max(a.maxp,b.maxp);
    x.maxi=max(a.maxi,b.maxi);
    if(a.mini==-1)
        x.mini=b.mini;
    else if(b.mini==-1)
        x.mini=a.mini;
    else
        x.mini=min(a.mini,b.mini);
    if(a.minp==-1)
        x.minp=b.minp;
    else if(b.minp==-1)
        x.minp=a.minp;
    else
        x.minp=min(a.minp,b.minp);
    return x;
}

void propag(long long poz)
{
    if(aint[poz].lazy%2==1)
    {
        swap(aint[poz].maxi,aint[poz].maxp);
        swap(aint[poz].mini,aint[poz].minp);
    }
    if(aint[poz].maxp!=-1)
        aint[poz].maxp+=aint[poz].lazy;
    if(aint[poz].maxi!=-1)
        aint[poz].maxi+=aint[poz].lazy;
    if(aint[poz].minp!=-1)
        aint[poz].minp+=aint[poz].lazy;
    if(aint[poz].mini!=-1)
        aint[poz].mini+=aint[poz].lazy;
    aint[2*poz].lazy+=aint[poz].lazy;
    aint[2*poz+1].lazy+=aint[poz].lazy;
    aint[poz].lazy=0;
}

void build(long long poz, long long st, long long dr)
{
    if(st==dr)
    {
        if(v[st]%2==0)
        {
            aint[poz].maxp=v[st];
            aint[poz].minp=v[st];
            aint[poz].maxi=-1;
            aint[poz].mini=-1;
        }
        else
        {
            aint[poz].maxi=v[st];
            aint[poz].mini=v[st];
            aint[poz].maxp=-1;
            aint[poz].minp=-1;
        }
        return;
    }
    long long mid=(st+dr)/2;
    build(2*poz,st,mid);
    build(2*poz+1,mid+1,dr);
    aint[poz]=join(aint[2*poz],aint[2*poz+1]);
}

nod query(long long poz, long long st, long long dr, long long a, long long b)
{
    propag(poz);
    if(a<=st && dr<=b)
        return aint[poz];
    long long mid=(st+dr)/2;
    if(b<=mid)
        return query(2*poz,st,mid,a,b);
    if(mid+1<=a)
        return query(2*poz+1,mid+1,dr,a,b);
    return join(query(2*poz,st,mid,a,b),query(2*poz+1,mid+1,dr,a,b));
}


void update(long long poz, long long st, long long dr, long long a, long long b, long long val)
{
    propag(poz);
    if(a<=st && dr<=b)
    {
        aint[poz].lazy=val;
        propag(poz);
        return;
    }
    long long mid=(st+dr)/2;
    if(a<=mid)
        update(2*poz,st,mid,a,b,val);
    else
        propag(2*poz);
    if(mid+1<=b)
        update(2*poz+1,mid+1,dr,a,b,val);
    else
        propag(2*poz+1);
    aint[poz]=join(aint[2*poz],aint[2*poz+1]);
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    long long n;
    cin>>n;
    for(long long i=1; i<=n; i++)
        cin>>v[i];
    build(1,1,n);
    long long q;
    cin>>q;
    for(long long i=0; i<q; i++)
    {
        long long cer;
        cin>>cer;
        if(cer==1)
        {
            long long a,b;
            cin>>a>>b;
            nod x=query(1,1,n,a,b);
            cout<<x.minp<<" "<<x.maxi<<'\n';
        }
        else
        {
            long long a,b,val;
            cin>>a>>b>>val;
            update(1,1,n,a,b,val);
        }
    }
}

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