Submission #691657

#	Time	Username	Problem	Language	Result	Execution time	Memory
691657		MateiKing80	Simple (info1cup19_simple)	C++14	0 / 100	300 ms	8788 KiB

subway

#include <iostream>

using namespace std;
struct sus
{
    int maxpar=-1,minpar=-1,maximpar=-1,minimpar=-1,lazy=0;
}aint[400005];
int v[200005];

sus join(sus a, sus b)
{
    sus x;
    x.lazy=0;
    if(a.maxpar==-1)
    {
        x.maxpar=b.maxpar;
        x.minpar=b.minpar;
    }
    else if(b.maxpar==-1)
    {
        x.maxpar=a.maxpar;
        x.minpar=a.minpar;
    }
    else
        x.maxpar=max(a.maxpar,b.maxpar),x.minpar=min(a.minpar,b.minpar);
    if(a.maximpar==-1)
    {
        x.maximpar=b.maximpar;
        x.minimpar=b.minimpar;
    }
    else if(b.maximpar==-1)
    {
        x.maximpar=a.maximpar;
        x.minimpar=a.minimpar;
    }
    else
        x.maximpar=max(a.maximpar,b.maximpar),x.minimpar=min(a.minimpar,b.minimpar);
}

pair<int,int>join2(pair<int,int>a, pair<int,int>b)
{
    if(a.first==-1)
        return {b.first, max(a.first,b.second)};
    if(b.first==-1)
        return {a.first, max(a.first,b.second)};
    return {min(a.first,b.first), max(a.first,b.second)};

}
void build(int poz, int st, int dr)
{
    if(st==dr)
    {
        if(v[st]%2==0)
            aint[poz].maxpar=v[st],aint[poz].minimpar=-1,aint[poz].minpar=v[st],aint[poz].maximpar=-1;
        else
            aint[poz].maximpar=v[st],aint[poz].minpar=-1,aint[poz].minimpar=v[st],aint[poz].maxpar=-1;
        return;
    }
    int mid=(st+dr)/2;
    build(2*poz,st,mid);
    build(2*poz+1,mid+1,dr);
}

void propag(int poz, int st, int dr, int x)
{
    if(x%2==0)
    {
        if(aint[poz].maxpar!=-1)
            aint[poz].maxpar+=x;
        if(aint[poz].minpar!=-1)
            aint[poz].minpar+=x;
        if(aint[poz].maximpar!=-1)
            aint[poz].maximpar+=x;
        if(aint[poz].minimpar!=-1)
            aint[poz].minimpar+=x;
    }
    else
    {
        sus a=aint[poz];
        if(a.maxpar!=-1)
            aint[poz].maximpar+=x;
        if(a.minpar!=-1)
            aint[poz].minimpar+=x;
        if(a.maximpar!=-1)
            aint[poz].maxpar+=x;
        if(a.minimpar!=-1)
            aint[poz].minpar+=x;
    }
    if(st!=dr)
    {
        aint[2*poz].lazy+=x;
        aint[2*poz+1].lazy+=x;
    }
    aint[poz].lazy=0;
    return;
}


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

pair<int,int> query(int poz,int st, int dr, int a, int b)
{
    propag(poz, st, dr, aint[poz].lazy);
    if(a<=st && dr<=b)
        return {aint[poz].minpar,aint[poz].maximpar};
    int 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 join2(query(2*poz,st,mid,a,b),query(2*poz+1,mid+1,dr,a,b));
}

int main()
{
    int n,q;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>v[i];
    build(1,1,n);
    cin>>q;
    for(int i=0;i<q;i++)
    {
        int tip,a,b,c;
        cin>>tip>>a>>b;
        if(tip==0)
        {
            cin>>c;
            update(1,1,n,a,b,c);
        }
        else
        {
            pair<int,int>u=query(1,1,n,a,b);
            cout<<u.first<<" "<<u.second<<'\n';
        }
    }
    return 0;
}
///L

Compilation message (stderr)

subway.cpp: In function 'sus join(sus, sus)':
subway.cpp:38:1: warning: no return statement in function returning non-void [-Wreturn-type]
   38 | }
      | ^

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