Submission #641184

#	Time	Username	Problem	Language	Result	Execution time	Memory
641184		Tenis0206	Weirdtree (RMI21_weirdtree)	C++14	100 / 100	1360 ms	52044 KiB

weirdtree

#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 / 5
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 19 / 19
• Subtask 5: 10 / 10
• Subtask 6: 21 / 21
• Subtask 7: 29 / 29