Submission #982519

#	Time	Username	Problem	Language	Result	Execution time	Memory
982519		AndrijaM	Simple (info1cup19_simple)	C++14	30 / 100	1014 ms	10888 KiB

subway

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int maxn=2e5+10;


int n,q;
int x[maxn];
int lz[4*maxn];
pair<pair<int,int>,pair<int,int>>st[4*maxn];

void btree(int L,int R,int pos)
{
    if(L==R)
    {
        if(x[L]%2==0)
        {
            st[pos].first.first=x[L];
            st[pos].first.second=x[L];
            st[pos].second.first=1e18;
            st[pos].second.second=-1e18;
        }
        else
        {
            st[pos].first.first=1e18;
            st[pos].first.second=-1e18;
            st[pos].second.first=x[L];
            st[pos].second.second=x[L];
        }
        return ;
    }
    int mid=(L+R)/2;
    btree(L,mid,2*pos);
    btree(mid+1,R,2*pos+1);
    st[pos].first.first=min(st[2*pos].first.first,st[2*pos+1].first.first);
    st[pos].first.second=max(st[2*pos].first.second,st[2*pos+1].first.second);
    st[pos].second.first=min(st[2*pos].second.first,st[2*pos+1].second.first);
    st[pos].second.second=max(st[2*pos].second.second,st[2*pos+1].second.second);
}

void u(long long L,long long R,long long i,long long j,long long nval,long long pos)
{
    if(lz[pos]!=0)
    {
        int P1=st[pos].first.first;
        int P2=st[pos].first.second;
        int N1=st[pos].second.first;
        int N2=st[pos].second.second;
        if(lz[pos]%2==0)
        {
            if(st[pos].first.first!=1e18 && st[pos].first.first!=-1e18)
            st[pos].first.first=st[pos].first.first+lz[pos];
            if(st[pos].first.second!=1e18 && st[pos].first.second!=-1e18)
            st[pos].first.second=st[pos].first.second+lz[pos];
            if(st[pos].second.first!=1e18 && st[pos].second.first!=-1e18)
            st[pos].second.first=st[pos].second.first+lz[pos];
            if(st[pos].second.second!=1e18 && st[pos].second.second!=-1e18)
            st[pos].second.second=st[pos].second.second+lz[pos];
        }
        else
        {
            if(N1!=1e18 && N1!=-1e18)
            N1+=lz[pos];
            if(N2!=1e18 && N2!=-1e18)
            N2+=lz[pos];
            if(P1!=1e18 && P1!=-1e18)
            P1+=lz[pos];
            if(P2!=1e18 && P2!=-1e18)
            P2+=lz[pos];

            st[pos].first.first=N1;
            st[pos].first.second=N2;
            st[pos].second.first=P1;
            st[pos].second.second=P2;
        }
        if(L!=R)
        {
            lz[2*pos]+=lz[pos];
            lz[2*pos+1]+=lz[pos];
        }
        lz[pos]=0;
    }
    if(i>R || j<L)
    {
        return ;
    }
    if(i<=L && R<=j)
    {
        int P1=st[pos].first.first;
        int P2=st[pos].first.second;
        int N1=st[pos].second.first;
        int N2=st[pos].second.second;
        if(nval%2==0)
        {
            if(st[pos].first.first!=1e18 && st[pos].first.first!=-1e18)
            st[pos].first.first=st[pos].first.first+nval;
            if(st[pos].first.second!=1e18 && st[pos].first.second!=-1e18)
            st[pos].first.second=st[pos].first.second+nval;
            if(st[pos].second.first!=1e18 && st[pos].second.first!=-1e18)
            st[pos].second.first=st[pos].second.first+nval;
            if(st[pos].second.second!=1e18 && st[pos].second.second!=-1e18)
            st[pos].second.second=st[pos].second.second+nval;
        }
        else
        {
            if(N1!=1e18 && N1!=-1e18)
            N1+=nval;
            if(N2!=1e18 && N2!=-1e18)
            N2+=nval;
            if(P1!=1e18 && P1!=-1e18)
            P1+=nval;
            if(P2!=1e18 && P2!=-1e18)
            P2+=nval;

            st[pos].first.first=N1;
            st[pos].first.second=N2;
            st[pos].second.first=P1;
            st[pos].second.second=P2;
        }
        if(L!=R)
        {
            lz[2*pos]+=nval;
            lz[2*pos+1]+=nval;
        }
        return ;
    }
    long long mid=(L+R)/2;
    u(L,mid,i,j,nval,2*pos);
    u(mid+1,R,i,j,nval,2*pos+1);
    st[pos].first.first=min(st[2*pos].first.first,st[2*pos+1].first.first);
    st[pos].first.second=max(st[2*pos].first.second,st[2*pos+1].first.second);
    st[pos].second.first=min(st[2*pos].second.first,st[2*pos+1].second.first);
    st[pos].second.second=max(st[2*pos].second.second,st[2*pos+1].second.second);
}

pair<int,int> query(long long L,long long R,long long i,long long j,long long pos)
{
    if(lz[pos]!=0)
    {
        int P1=st[pos].first.first;
        int P2=st[pos].first.second;
        int N1=st[pos].second.first;
        int N2=st[pos].second.second;
        if(lz[pos]%2==0)
        {
            if(st[pos].first.first!=1e18 && st[pos].first.first!=-1e18)
            st[pos].first.first=st[pos].first.first+lz[pos];
            if(st[pos].first.second!=1e18 && st[pos].first.second!=-1e18)
            st[pos].first.second=st[pos].first.second+lz[pos];
            if(st[pos].second.first!=1e18 && st[pos].second.first!=-1e18)
            st[pos].second.first=st[pos].second.first+lz[pos];
            if(st[pos].second.second!=1e18 && st[pos].second.second!=-1e18)
            st[pos].second.second=st[pos].second.second+lz[pos];
        }
        else
        {
            if(N1!=1e18 && N1!=-1e18)
            N1+=lz[pos];
            if(N2!=1e18 && N2!=-1e18)
            N2+=lz[pos];
            if(P1!=1e18 && P1!=-1e18)
            P1+=lz[pos];
            if(P2!=1e18 && P2!=-1e18)
            P2+=lz[pos];

            st[pos].first.first=N1;
            st[pos].first.second=N2;
            st[pos].second.first=P1;
            st[pos].second.second=P2;
        }
        if(L!=R)
        {
            lz[2*pos]+=lz[pos];
            lz[2*pos+1]+=lz[pos];
        }
        lz[pos]=0;
    }
    if(R<i || j<L)
    {
        return {1e18,-1e18};
    }
    if(i<=L && R<=j)
    {
        return {st[pos].first.first,st[pos].second.second};
    }
    long long mid=(L+R)/2;
    return {min(query(L,mid,i,j,2*pos).first,query(mid+1,R,i,j,2*pos+1).first),max(query(L,mid,i,j,2*pos).second,query(mid+1,R,i,j,2*pos+1).second)};
}

signed main()
{
    ios::sync_with_stdio(false);
    ///ifstream cin("scara.in");
    ///ofstream cout("scara.out");
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>x[i];
        ///u(0,n-1,i,i,x[i],1);
    }
    cin>>q;
    btree(0,n-1,1);
    while(q--)
    {
        int t;
        cin>>t;
        if(t==1)
        {
            int a,b;
            cin>>a>>b;
            a--;b--;
            pair<int,int>p;
            p=query(0,n-1,a,b,1);
            if(p.first==1e18)
            {
                p.first=-1;
            }
            if(p.second==-1e18)
            {
                p.second=-1;
            }
            cout<<p.first<<" "<<p.second<<endl;
        }
        else
        {
            int a,b,c;
            cin>>a>>b>>c;
            a--;b--;
            u(0,n-1,a,b,c,1);
        }
    }
    return 0;
}

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