oj.uz

Submission #982519

# Submission time Handle Problem Language Result Execution time Memory
982519 2024-05-14T10:40:41 Z AndrijaM Simple (info1cup19_simple) C++14
30 / 100
 1000 ms 10888 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 2904 KB Output is correct
2 Correct 179 ms 3192 KB Output is correct
3 Correct 296 ms 3040 KB Output is correct
4 Correct 456 ms 3060 KB Output is correct
5 Correct 405 ms 3068 KB Output is correct
6 Correct 455 ms 3032 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1014 ms 10888 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 2904 KB Output is correct
2 Correct 179 ms 3192 KB Output is correct
3 Correct 296 ms 3040 KB Output is correct
4 Correct 456 ms 3060 KB Output is correct
5 Correct 405 ms 3068 KB Output is correct
6 Correct 455 ms 3032 KB Output is correct
7 Execution timed out 1014 ms 10888 KB Time limit exceeded
8 Halted 0 ms 0 KB -