Submission #230020

#	Time	Username	Problem	Language	Result	Execution time	Memory
230020		Tenis0206	Simple (info1cup19_simple)	C++11	100 / 100	410 ms	32716 KiB

subway

#include <bits/stdc++.h>

using namespace std;
long long n,q,ai1[1000005],ai2[1000005],ai3[1000005],ai4[1000005],lazy[1000005],v[200005];
const long long oo = 1LL*INT_MAX*INT_MAX;
void propag(long long nod, long long a, long long b)
{
    if(a==b || lazy[nod]==0)
        return;
    lazy[nod*2]+=lazy[nod];
    lazy[nod*2+1]+=lazy[nod];

    if(ai1[nod*2]!=oo)
        ai1[nod*2]+=lazy[nod];
    if(ai1[nod*2+1]!=oo)
        ai1[nod*2+1]+=lazy[nod];

    if(ai2[nod*2]!=oo)
        ai2[nod*2]+=lazy[nod];
    if(ai2[nod*2+1]!=oo)
        ai2[nod*2+1]+=lazy[nod];

    if(ai3[nod*2]!=-oo)
        ai3[nod*2]+=lazy[nod];
    if(ai3[nod*2+1]!=-oo)
        ai3[nod*2+1]+=lazy[nod];

    if(ai4[nod*2]!=-oo)
        ai4[nod*2]+=lazy[nod];
    if(ai4[nod*2+1]!=-oo)
        ai4[nod*2+1]+=lazy[nod];

    if(lazy[nod]%2)
    {
        swap(ai1[nod*2],ai2[nod*2]);
        swap(ai1[nod*2+1],ai2[nod*2+1]);
        swap(ai3[nod*2],ai4[nod*2]);
        swap(ai3[nod*2+1],ai4[nod*2+1]);
    }
    lazy[nod]=0;
}
void update(long long ua, long long ub, long long val, long long nod, long long a, long long b)
{
    if(ua<=a && ub>=b)
    {
        lazy[nod]+=val;
        if(ai1[nod]!=oo)
            ai1[nod]+=val;
        if(ai2[nod]!=oo)
            ai2[nod]+=val;
        if(ai3[nod]!=-oo)
            ai3[nod]+=val;
        if(ai4[nod]!=-oo)
            ai4[nod]+=val;
        if(val%2)
        {
            swap(ai1[nod],ai2[nod]);
            swap(ai3[nod],ai4[nod]);
        }
        return;
    }
    propag(nod,a,b);
    long long mij=(a+b)/2;
    if(ua<=mij)
    {
        update(ua,ub,val,nod*2,a,mij);
    }
    if(ub>mij)
    {
        update(ua,ub,val,nod*2+1,mij+1,b);
    }
    ai1[nod]=min(ai1[nod*2],ai1[nod*2+1]);
    ai2[nod]=min(ai2[nod*2],ai2[nod*2+1]);
    ai3[nod]=max(ai3[nod*2],ai3[nod*2+1]);
    ai4[nod]=max(ai4[nod*2],ai4[nod*2+1]);
}
pair<long long,long long> query(long long qa, long long qb, long long nod, long long a, long long b)
{
    if(qa<=a && qb>=b)
    {
        return {ai1[nod],ai3[nod]};
    }
    propag(nod,a,b);
    long long mij=(a+b)/2;
    pair<long long,long long> rez1={oo,-oo},rez2={oo,-oo};
    if(qa<=mij)
    {
        rez1=query(qa,qb,nod*2,a,mij);
    }
    if(qb>mij)
    {
        rez2=query(qa,qb,nod*2+1,mij+1,b);
    }
    return {min(rez1.first,rez2.first),max(rez1.second,rez2.second)};
}
void update_in(long long poz, long long val, long long nod, long long a, long long b)
{
    if(a==b)
    {
        if(val%2==0)
        {
            ai1[nod]=ai4[nod]=val;
            ai2[nod]=oo;
            ai3[nod]=-oo;
        }
        else if(val%2==1)
        {
            ai2[nod]=ai3[nod]=val;
            ai1[nod]=oo;
            ai4[nod]=-oo;
        }
        return;
    }
    long long mij=(a+b)/2;
    if(poz<=mij)
    {
        update_in(poz,val,nod*2,a,mij);
    }
    else
    {
        update_in(poz,val,nod*2+1,mij+1,b);
    }
    ai1[nod]=min(ai1[nod*2],ai1[nod*2+1]);
    ai2[nod]=min(ai2[nod*2],ai2[nod*2+1]);
    ai3[nod]=max(ai3[nod*2],ai3[nod*2+1]);
    ai4[nod]=max(ai4[nod*2],ai4[nod*2+1]);
}
int main()
{
    //freopen("hard.in","r",stdin);
    //freopen("hard.out","w",stdout);
    ///1 for minimum even number
    ///2 for minimum odd number
    ///3 for maximum odd number
    ///4 for maximum even number
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(long long i=1;i<=n;i++)
    {
        cin>>v[i];
        update_in(i,v[i],1,1,n);
    }
    cin>>q;
    for(long long i=1;i<=q;i++)
    {
        long long t,a,b,val;
        cin>>t;
        if(t==0)
        {
            cin>>a>>b>>val;
            if(a>b)
                continue;
            update(a,b,val,1,1,n);
        }
        else if(t==1)
        {
            cin>>a>>b;
            if(a>b)
            {
                cout<<"-1 -1"<<'\n';
            }
            pair<long long,long long> rez=query(a,b,1,1,n);
            if(rez.first==oo)
            {
                cout<<-1<<' ';
            }
            else
            {
                cout<<rez.first<<' ';
            }
            if(rez.second==-oo)
            {
                cout<<-1<<'\n';
            }
            else
            {
                cout<<rez.second<<'\n';
            }
        }
    }
    return 0;
}

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