oj.uz

Submission #641184

# Submission time Handle Problem Language Result Execution time Memory
641184 2022-09-16T07:16:59 Z Tenis0206 Weirdtree (RMI21_weirdtree) C++14
100 / 100
 1360 ms 52044 KB 
#include <bits/stdc++.h>
//#define home

#ifndef home

#include "weirdtree.h"

#endif // home

using namespace std;

const long long oo = LLONG_MAX;

struct node
{
    long long sum,Max1,fr,Max2;
};

int n,q;
int v[300005];

node ai[1200005];
long long lazy[1200005];

node Merge(node st, node dr)
{
    node rez;
    rez.sum = st.sum + dr.sum;
    if(st.Max1==dr.Max1)
    {
        rez.Max1 = st.Max1;
        rez.fr = st.fr + dr.fr;
        rez.Max2 = max(st.Max2,dr.Max2);
        return rez;
    }
    if(st.Max1 > dr.Max1)
    {
        rez.Max1 = st.Max1;
        rez.fr = st.fr;
        rez.Max2 = max(st.Max2,dr.Max1);
        return rez;
    }
    rez.Max1 = dr.Max1;
    rez.fr = dr.fr;
    rez.Max2 = max(dr.Max2,st.Max1);
    return rez;
}

void propag(int nod)
{
    if(lazy[nod]==oo)
    {
        return;
    }
    if(ai[nod*2].Max1 > lazy[nod])
    {
        ai[nod*2].sum -= (ai[nod*2].Max1 - lazy[nod]) * ai[nod*2].fr;
        ai[nod*2].Max1 = lazy[nod];
        lazy[nod*2] = min(lazy[nod*2],lazy[nod]);
    }
    if(ai[nod*2+1].Max1 > lazy[nod])
    {
        ai[nod*2+1].sum -= (ai[nod*2+1].Max1 - lazy[nod]) * ai[nod*2+1].fr;
        ai[nod*2+1].Max1 = lazy[nod];
        lazy[nod*2+1] = min(lazy[nod*2+1],lazy[nod]);
    }
    lazy[nod] = oo;
}

void update_poz(int poz, long long val, int nod, int a, int b)
{
    if(a==b)
    {
        ai[nod].sum = val;
        ai[nod].Max1 = val;
        ai[nod].fr = 1;
        ai[nod].Max2 = INT_MIN;
        return;
    }
    int mij = (a + b) >> 1;
    propag(nod);
    if(poz<=mij)
    {
        update_poz(poz,val,nod*2,a,mij);
    }
    else
    {
        update_poz(poz,val,nod*2+1,mij+1,b);
    }
    ai[nod] = Merge(ai[nod*2],ai[nod*2+1]);
}

void update(int ua, int ub, long long val, int nod, int a, int b)
{
    if(ai[nod].Max1 < val)
    {
        return;
    }
    if(ua<=a && ub>=b && val > ai[nod].Max2)
    {
        ai[nod].sum -= (ai[nod].Max1 - val) * ai[nod].fr;
        ai[nod].Max1 = val;
        lazy[nod] = min(lazy[nod],val);
        return;
    }
    propag(nod);
    int mij = (a + b) >> 1;
    if(ua<=mij)
    {
        update(ua,ub,val,nod*2,a,mij);
    }
    if(ub>mij)
    {
        update(ua,ub,val,nod*2+1,mij+1,b);
    }
    ai[nod] = Merge(ai[nod*2],ai[nod*2+1]);
}

node query(int qa, int qb, int nod, int a, int b)
{
    if(qa<=a && qb>=b)
    {
        return ai[nod];
    }
    int mij = (a + b) >> 1;
    propag(nod);
    if(qa<=mij && qb>mij)
    {
        return Merge(query(qa,qb,nod*2,a,mij),query(qa,qb,nod*2+1,mij+1,b));
    }
    if(qa<=mij)
    {
        return query(qa,qb,nod*2,a,mij);
    }
    return query(qa,qb,nod*2+1,mij+1,b);
}

void preset(int nod, int a, int b)
{
    lazy[nod] = oo;
    ai[nod].fr = 0;
    ai[nod].Max1 = 0;
    ai[nod].Max2 = INT_MIN;
    ai[nod].sum = 0;
    if(a==b)
    {
        return;
    }
    int mij = (a + b) >> 1;
    preset(nod*2,a,mij);
    preset(nod*2+1,mij+1,b);
}

void cut(int l, int r, int k)
{
    while(k > 0)
    {
        node val = query(l,r,1,1,n);
        if((val.Max1 - val.Max2) * val.fr <= k)
        {
            k -= (val.Max1 - val.Max2) * val.fr;
            update(l,r,val.Max2,1,1,n);
            continue;
        }
        long long dif = k / val.fr;
        k = k % val.fr;
        if(val.Max1 - dif <= 0)
        {
            update(l,r,0,1,1,n);
            break;
        }
        update(l,r,val.Max1-dif,1,1,n);
        val = query(l,r,1,1,n);
        if(k)
        {
            int st = l;
            int dr = r;
            int poz = 0;
            while(st<=dr)
            {
                int mij = (st + dr) >> 1;
                node aux = query(l,mij,1,1,n);
                if(aux.Max1==val.Max1 && aux.fr>=k)
                {
                    poz = mij;
                    dr = mij - 1;
                }
                else
                {
                    st = mij + 1;
                }
            }
            update(l,poz,val.Max1-1,1,1,n);
            k = 0;
        }
    }
}

void magic(int poz, int val)
{
    update_poz(poz,val,1,1,n);
}

long long inspect(int l, int r)
{
    return query(l,r,1,1,n).sum;
}

void initialise(int N, int Q, int h[])
{
    n = N;
    q = Q;
    preset(1,1,n);
    for(int i=1;i<=n;i++)
    {
        update_poz(i,h[i],1,1,n);
    }
}

#ifdef home

signed main()
{
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
    cin>>n>>q;
    for(int i=1; i<=n; i++)
    {
        cin>>v[i];
    }
    initialize(n,q,v);
    for(int i=1; i<=q; i++)
    {
        int tip;
        cin>>tip;
        if(tip==1)
        {
            int l,r,k;
            cin>>l>>r>>k;
            cut(l,r,k);
        }
        else if(tip==2)
        {
            int poz,val;
            cin>>poz>>val;
            magic(poz,val);
        }
        else
        {
            int l,r;
            cin>>l>>r;
            cout<<inspect(l,r)<<'\n';
        }
    }
    return 0;
}

#endif // home

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 74 ms 13252 KB Output is correct
4 Correct 184 ms 13280 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 4 ms 468 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 1301 ms 47764 KB Output is correct
4 Correct 519 ms 47896 KB Output is correct
5 Correct 1360 ms 47940 KB Output is correct
6 Correct 465 ms 47820 KB Output is correct
7 Correct 26 ms 13000 KB Output is correct
8 Correct 184 ms 12744 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 13000 KB Output is correct
2 Correct 184 ms 12744 KB Output is correct
3 Correct 477 ms 47228 KB Output is correct
4 Correct 552 ms 47332 KB Output is correct

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 74 ms 13252 KB Output is correct
4 Correct 184 ms 13280 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 26 ms 13000 KB Output is correct
8 Correct 184 ms 12744 KB Output is correct
9 Correct 78 ms 13300 KB Output is correct
10 Correct 166 ms 13240 KB Output is correct
11 Correct 90 ms 13228 KB Output is correct
12 Correct 163 ms 13352 KB Output is correct
13 Correct 87 ms 13392 KB Output is correct

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 74 ms 13252 KB Output is correct
4 Correct 184 ms 13280 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 1301 ms 47764 KB Output is correct
8 Correct 519 ms 47896 KB Output is correct
9 Correct 1360 ms 47940 KB Output is correct
10 Correct 465 ms 47820 KB Output is correct
11 Correct 477 ms 47228 KB Output is correct
12 Correct 552 ms 47332 KB Output is correct
13 Correct 78 ms 13300 KB Output is correct
14 Correct 166 ms 13240 KB Output is correct
15 Correct 90 ms 13228 KB Output is correct
16 Correct 163 ms 13352 KB Output is correct
17 Correct 87 ms 13392 KB Output is correct
18 Correct 26 ms 13000 KB Output is correct
19 Correct 184 ms 12744 KB Output is correct
20 Correct 382 ms 51620 KB Output is correct
21 Correct 930 ms 52044 KB Output is correct
22 Correct 493 ms 51860 KB Output is correct
23 Correct 919 ms 51964 KB Output is correct
24 Correct 404 ms 51768 KB Output is correct