oj.uz

답안 #231331

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
231331 2020-05-13T11:24:43 Z filiptudose7 Simple (info1cup19_simple) C++11
30 / 100
 300 ms 27000 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 bignumber = 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]!=bignumber)
        ai1[nod*2]+=lazy[nod];
    if(ai1[nod*2+1]!=bignumber)
        ai1[nod*2+1]+=lazy[nod];

    if(ai2[nod*2]!=bignumber)
        ai2[nod*2]+=lazy[nod];
    if(ai2[nod*2+1]!=bignumber)
        ai2[nod*2+1]+=lazy[nod];

    if(ai3[nod*2]!=-bignumber)
        ai3[nod*2]+=lazy[nod];
    if(ai3[nod*2+1]!=-bignumber)
        ai3[nod*2+1]+=lazy[nod];

    if(ai4[nod*2]!=-bignumber)
        ai4[nod*2]+=lazy[nod];
    if(ai4[nod*2+1]!=-bignumber)
        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(ai4[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]!=bignumber)
            ai1[nod]+=val;
        if(ai2[nod]!=bignumber)
            ai2[nod]+=val;
        if(ai3[nod]!=-bignumber)
            ai3[nod]+=val;
        if(ai4[nod]!=-bignumber)
            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={bignumber,-bignumber},rez2={bignumber,-bignumber};
    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]=bignumber;
            ai3[nod]=-bignumber;
        }
        else if(val%2==1)
        {
            ai2[nod]=ai3[nod]=val;
            ai1[nod]=bignumber;
            ai4[nod]=-bignumber;
        }
        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("in","r",stdin);
    //freopen("out","w",stdout);
    cin.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==bignumber)
            {
                cout<<-1<<' ';
            }
            else
            {
                cout<<rez.first<<' ';
            }
            if(rez.second==-bignumber)
            {
                cout<<-1<<'\n';
            }
            else
            {
                cout<<rez.second<<'\n';
            }
        }
    }
    return 0;
}

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 137 ms 13560 KB Output is correct
2 Correct 299 ms 26872 KB Output is correct
3 Correct 286 ms 26916 KB Output is correct
4 Correct 300 ms 27000 KB Output is correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 896 KB Output isn't correct
2 Halted 0 ms 0 KB -