Submission #231685

#	Time	Username	Problem	Language	Result	Execution time	Memory
231685		stefantaga	Simple (info1cup19_simple)	C++14	100 / 100	490 ms	31100 KiB

subway

#include <bits/stdc++.h>
#define INF 10000000000000000
using namespace std;
struct wow
{
    long long minimpar,minpar,maximpar,maximimpar;
}arb[800005];
long long lazy[800005];
void construieste (int st,int dr,int nod ,int poz ,long long val)
{
    if (st==dr)
    {
        if (val%2==1)
        {
            arb[nod].minimpar=arb[nod].maximimpar=val;
            arb[nod].minpar=INF;
            arb[nod].maximpar=-INF;
        }
        else
        {
            arb[nod].minpar=arb[nod].maximpar=val;
            arb[nod].minimpar=INF;
            arb[nod].maximimpar=-INF;
        }
        return ;
    }
    int mij=(st+dr)/2;
    if (mij>=poz)
    {
        construieste(st,mij,2*nod,poz,val);
    }
    else
    {
        construieste(mij+1,dr,2*nod+1,poz,val);
    }
    arb[nod].maximpar=max(arb[2*nod].maximpar,arb[2*nod+1].maximpar);
    arb[nod].minpar=min(arb[2*nod].minpar,arb[2*nod+1].minpar);
    arb[nod].maximimpar=max(arb[2*nod].maximimpar,arb[2*nod+1].maximimpar);
    arb[nod].minimpar=min(arb[2*nod].minimpar,arb[2*nod+1].minimpar);
}
void aduna (int nod,long long val)
{
    if (arb[nod].minimpar!=INF)
        {
            arb[nod].minimpar+=val;
        }
        if (arb[nod].minpar!=INF)
        {
            arb[nod].minpar+=val;
        }
        if (arb[nod].maximimpar!=-INF)
        {
            arb[nod].maximimpar+=val;
        }
        if (arb[nod].maximpar!=-INF)
        {
            arb[nod].maximpar+=val;
        }
        if (val%2==1)
        {
            swap(arb[nod].minpar,arb[nod].minimpar);
            swap(arb[nod].maximimpar,arb[nod].maximpar);
        }
}
void propaga (int st,int dr,int nod)
{
    if (st>dr||lazy[nod]==0)
    {
        return;
    }
    lazy[2*nod+1]+=lazy[nod];
    lazy[2*nod]+=lazy[nod];
    aduna(2*nod,lazy[nod]);
    aduna(2*nod+1,lazy[nod]);
    lazy[nod]=0;
}
void update (int st,int dr,int nod,int ua,int ub,long long val)
{
    if (ua<=st&&dr<=ub)
    {
        lazy[nod]+=val;
        aduna(nod,val);
        return ;
    }
    propaga(st,dr,nod);
    int mij=(st+dr)/2;
    if (ua<=mij)
    {
        update (st,mij,2*nod,ua,ub,val);
    }
    if (mij<ub)
    {
        update (mij+1,dr,2*nod+1,ua,ub,val);
    }
    arb[nod].maximpar=max(arb[2*nod].maximpar,arb[2*nod+1].maximpar);
    arb[nod].minpar=min(arb[2*nod].minpar,arb[2*nod+1].minpar);
    arb[nod].maximimpar=max(arb[2*nod].maximimpar,arb[2*nod+1].maximimpar);
    arb[nod].minimpar=min(arb[2*nod].minimpar,arb[2*nod+1].minimpar);
}
long long minim,maxim;
void query (int st,int dr,int nod ,int ua ,int ub,int tip)
{
    if (ua<=st&&dr<=ub)
    {
        if (tip==0)
        {
            minim=min(minim,arb[nod].minpar);
        }
        else
        {
            maxim=max(maxim,arb[nod].maximimpar);
        }
        return;
    }
    propaga(st,dr,nod);
    int mij=(st+dr)/2;
    if (ua<=mij)
    {
        query (st,mij,2*nod,ua,ub,tip);
    }
    if (mij<ub)
    {
        query (mij+1,dr,2*nod+1,ua,ub,tip);
    }
}
int n,i,x,m,tip;
long long a,b,val;
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
    #ifdef HOME
    ifstream cin("date.in");
    ofstream cout("date.out");
    #endif // HOME
    cin>>n;
    for (i=1;i<=n;i++)
    {
        cin>>x;
        construieste(1,n,1,i,x);
    }
    cin>>m;
    for (i=1;i<=m;i++)
    {
        cin>>tip;
        if (tip==0)
        {
            cin>>a>>b>>val;
            update(1,n,1,a,b,val);
        }
        else
        {
            cin>>a>>b;
            minim=INF;
            query(1,n,1,a,b,0);
            if (minim==INF)
            {
                cout<<"-1"<<' ';
            }
            else
            {
                cout<<minim<<' ';
            }
            maxim=-INF;
            query(1,n,1,a,b,1);
            if (maxim==-INF)
            {
                cout<<"-1"<<'\n';
            }
            else
            {
                cout<<maxim<<'\n';
            }
        }
    }
    return 0;
}

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