oj.uz

Submission #230020

# Submission time Handle Problem Language Result Execution time Memory
230020 2020-05-07T19:01:43 Z Tenis0206 Simple (info1cup19_simple) C++11
100 / 100
 410 ms 32716 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 768 KB Output is correct
2 Correct 9 ms 896 KB Output is correct
3 Correct 11 ms 1280 KB Output is correct
4 Correct 10 ms 1280 KB Output is correct
5 Correct 11 ms 1280 KB Output is correct
6 Correct 11 ms 1280 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 11220 KB Output is correct
2 Correct 298 ms 21880 KB Output is correct
3 Correct 272 ms 21880 KB Output is correct
4 Correct 292 ms 22008 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 768 KB Output is correct
2 Correct 9 ms 896 KB Output is correct
3 Correct 11 ms 1280 KB Output is correct
4 Correct 10 ms 1280 KB Output is correct
5 Correct 11 ms 1280 KB Output is correct
6 Correct 11 ms 1280 KB Output is correct
7 Correct 134 ms 11220 KB Output is correct
8 Correct 298 ms 21880 KB Output is correct
9 Correct 272 ms 21880 KB Output is correct
10 Correct 292 ms 22008 KB Output is correct
11 Correct 175 ms 16120 KB Output is correct
12 Correct 410 ms 31480 KB Output is correct
13 Correct 385 ms 32120 KB Output is correct
14 Correct 402 ms 31480 KB Output is correct
15 Correct 353 ms 32716 KB Output is correct
16 Correct 152 ms 24824 KB Output is correct