oj.uz

Submission #733679

# Submission time Handle Problem Language Result Execution time Memory
733679 2023-05-01T07:51:34 Z MateiKing80 Simple (info1cup19_simple) C++14
100 / 100
 427 ms 53096 KB 
#include <iostream>

using namespace std;

long long v[200005];

struct nod
{
    long long maxp=-1,minp=-1,maxi=-1,mini=-1,lazy=0;
} aint[2000005];


nod join(nod a, nod b)
{
    nod x;
    x.lazy=0;
    x.maxp=max(a.maxp,b.maxp);
    x.maxi=max(a.maxi,b.maxi);
    if(a.mini==-1)
        x.mini=b.mini;
    else if(b.mini==-1)
        x.mini=a.mini;
    else
        x.mini=min(a.mini,b.mini);
    if(a.minp==-1)
        x.minp=b.minp;
    else if(b.minp==-1)
        x.minp=a.minp;
    else
        x.minp=min(a.minp,b.minp);
    return x;
}

void propag(long long poz)
{
    if(aint[poz].lazy%2==1)
    {
        swap(aint[poz].maxi,aint[poz].maxp);
        swap(aint[poz].mini,aint[poz].minp);
    }
    if(aint[poz].maxp!=-1)
        aint[poz].maxp+=aint[poz].lazy;
    if(aint[poz].maxi!=-1)
        aint[poz].maxi+=aint[poz].lazy;
    if(aint[poz].minp!=-1)
        aint[poz].minp+=aint[poz].lazy;
    if(aint[poz].mini!=-1)
        aint[poz].mini+=aint[poz].lazy;
    aint[2*poz].lazy+=aint[poz].lazy;
    aint[2*poz+1].lazy+=aint[poz].lazy;
    aint[poz].lazy=0;
}

void build(long long poz, long long st, long long dr)
{
    if(st==dr)
    {
        if(v[st]%2==0)
        {
            aint[poz].maxp=v[st];
            aint[poz].minp=v[st];
            aint[poz].maxi=-1;
            aint[poz].mini=-1;
        }
        else
        {
            aint[poz].maxi=v[st];
            aint[poz].mini=v[st];
            aint[poz].maxp=-1;
            aint[poz].minp=-1;
        }
        return;
    }
    long long mid=(st+dr)/2;
    build(2*poz,st,mid);
    build(2*poz+1,mid+1,dr);
    aint[poz]=join(aint[2*poz],aint[2*poz+1]);
}

nod query(long long poz, long long st, long long dr, long long a, long long b)
{
    propag(poz);
    if(a<=st && dr<=b)
        return aint[poz];
    long long 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 join(query(2*poz,st,mid,a,b),query(2*poz+1,mid+1,dr,a,b));
}


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


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    long long n;
    cin>>n;
    for(long long i=1; i<=n; i++)
        cin>>v[i];
    build(1,1,n);
    long long q;
    cin>>q;
    for(long long i=0; i<q; i++)
    {
        long long cer;
        cin>>cer;
        if(cer==1)
        {
            long long a,b;
            cin>>a>>b;
            nod x=query(1,1,n,a,b);
            cout<<x.minp<<" "<<x.maxi<<'\n';
        }
        else
        {
            long long a,b,val;
            cin>>a>>b>>val;
            update(1,1,n,a,b,val);
        }
    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1132 KB Output is correct
2 Correct 5 ms 1108 KB Output is correct
3 Correct 8 ms 1748 KB Output is correct
4 Correct 6 ms 1876 KB Output is correct
5 Correct 7 ms 1748 KB Output is correct
6 Correct 6 ms 1876 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 25752 KB Output is correct
2 Correct 320 ms 51332 KB Output is correct
3 Correct 332 ms 51348 KB Output is correct
4 Correct 305 ms 51444 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1132 KB Output is correct
2 Correct 5 ms 1108 KB Output is correct
3 Correct 8 ms 1748 KB Output is correct
4 Correct 6 ms 1876 KB Output is correct
5 Correct 7 ms 1748 KB Output is correct
6 Correct 6 ms 1876 KB Output is correct
7 Correct 147 ms 25752 KB Output is correct
8 Correct 320 ms 51332 KB Output is correct
9 Correct 332 ms 51348 KB Output is correct
10 Correct 305 ms 51444 KB Output is correct
11 Correct 183 ms 26264 KB Output is correct
12 Correct 383 ms 51996 KB Output is correct
13 Correct 362 ms 52628 KB Output is correct
14 Correct 427 ms 51792 KB Output is correct
15 Correct 337 ms 53096 KB Output is correct
16 Correct 100 ms 28848 KB Output is correct