Submission #646283

#	Time	Username	Problem	Language	Result	Execution time	Memory
646283		Kripton	Weirdtree (RMI21_weirdtree)	C++14	100 / 100	286 ms	37196 KiB

weirdtree

#include <bits/stdc++.h>
#include "weirdtree.h"
using namespace std;
int h[300001];
struct Beats
{
    int max1,max2,cntmax;
    long long sum;
} aint[1200001];
void combina(int nod)
{
    //suma
    aint[nod].sum=aint[2*nod].sum+aint[2*nod+1].sum;
    //maxim
    if(aint[2*nod].max1==aint[2*nod+1].max1)
    {
        aint[nod].max1=aint[2*nod].max1;
        aint[nod].cntmax=aint[2*nod].cntmax+aint[2*nod+1].cntmax;
        aint[nod].max2=max(aint[2*nod].max2,aint[2*nod+1].max2);
    }
    else
    {
        if(aint[2*nod].max1>aint[2*nod+1].max1)
        {
            aint[nod].max1=aint[2*nod].max1;
            aint[nod].cntmax=aint[2*nod].cntmax;
            aint[nod].max2=max(aint[2*nod].max2,aint[2*nod+1].max1);
        }
        else
        {
            aint[nod].max1=aint[2*nod+1].max1;
            aint[nod].cntmax=aint[2*nod+1].cntmax;
            aint[nod].max2=max(aint[2*nod].max1,aint[2*nod+1].max2);
        }
    }
}
void pushmin(int nod,int val)
{
    if(val>=aint[nod].max1)
        return;
    aint[nod].sum-=1LL*aint[nod].cntmax*aint[nod].max1;
    aint[nod].max1=val;
    aint[nod].sum+=1LL*aint[nod].cntmax*aint[nod].max1;
}
void pushdown(int nod)
{
    pushmin(2*nod,aint[nod].max1);
    pushmin(2*nod+1,aint[nod].max1);
}
void build(int nod,int st,int dr)
{
    if(st==dr)
    {
        aint[nod].max1=aint[nod].sum=h[st];
        aint[nod].max2=-1e9;
        aint[nod].cntmax=1;
        return;
    }
    int mid=(st+dr)/2;
    build(2*nod,st,mid);
    build(2*nod+1,mid+1,dr);
    combina(nod);
}
long long suma(int nod,int st,int dr,int a,int b)
{
    if(b<st||dr<a)
        return 0;
    if(a<=st&&dr<=b)
        return aint[nod].sum;
    pushdown(nod);
    int mid=(st+dr)/2;
    return suma(2*nod,st,mid,a,b)+suma(2*nod+1,mid+1,dr,a,b);
}
void WaverlyPlace(int nod,int st,int dr,int poz,int val)
{
    if(poz<st||dr<poz)
        return;
    if(st==poz&&poz==dr)
    {
        aint[nod].max1=aint[nod].sum=val;
        return;
    }
    pushdown(nod);
    int mid=(st+dr)/2;
    WaverlyPlace(2*nod,st,mid,poz,val);
    WaverlyPlace(2*nod+1,mid+1,dr,poz,val);
    combina(nod);
}
int x,vf,y;
void gimmeMax(int nod,int st,int dr,int a,int b)
{
    if(b<st||dr<a)
        return;
    if(a<=st&&dr<=b)
    {
        if(aint[nod].max1>x)
        {
            y=x;
            x=aint[nod].max1;
            vf=aint[nod].cntmax;
        }
        else if(aint[nod].max1==x)
            vf+=aint[nod].cntmax;
        else if(aint[nod].max1>y)
            y=aint[nod].max1;
        if(aint[nod].max2>y)
            y=aint[nod].max2;
        return;
    }
    pushdown(nod);
    int mid=(st+dr)/2;
    gimmeMax(2*nod,st,mid,a,b);
    gimmeMax(2*nod+1,mid+1,dr,a,b);
}
void updmin(int nod,int st,int dr,int a,int b,int val)
{
    if(b<st||dr<a||aint[nod].max1<val)
        return;
    if(a<=st&&dr<=b&&aint[nod].max2<val)
    {
        pushmin(nod,val);
        return;
    }
    pushdown(nod);
    int mid=(st+dr)/2;
    updmin(2*nod,st,mid,a,b,val);
    updmin(2*nod+1,mid+1,dr,a,b,val);
    combina(nod);
}
int updminpart(int nod,int st,int dr,int a,int b,int val,int cate)
{
    if(b<st||dr<a||aint[nod].max1<=val||cate<=0)
        return 0;
    if(a<=st&&dr<=b&&aint[nod].max2<val&&aint[nod].cntmax<=cate)
    {
        pushmin(nod,val);
        return aint[nod].cntmax;
    }
    pushdown(nod);
    int mid=(st+dr)/2;
    int x=updminpart(2*nod,st,mid,a,b,val,cate);
    int y=updminpart(2*nod+1,mid+1,dr,a,b,val,cate-x);
    combina(nod);
    return x+y;
}
int n,q;
void initialise ( int N, int Q, int H [])
{
    n=N;
    q=Q;
    for(int i=1; i<=n; i++)
        h[i]=H[i];
    build(1,1,n);
}
void cut ( int l, int r, int k )
{
    while(k)
    {
        vf=-1;
        x=y=-1e9;
        gimmeMax(1,1,n,l,r);
        y=max(y,0);
        if(x==0&&y==0)
            break;
        //cout<<x<<" "<<y<<" "<<vf<<'\n';
        if(k>=1LL*(x-y)*vf)
        {
            k-=1LL*(x-y)*vf;
            updmin(1,1,n,l,r,y);
        }
        else
        {
            int y=x-k/vf;
            if(y!=x)
                updmin(1,1,n,l,r,y);
            assert(updminpart(1,1,n,l,r,y-1,k%vf)==k%vf);
            k=0;
        }
    }
}
void magic ( int i, int x )
{
    WaverlyPlace(1,1,n,i,x);
}
long long int inspect ( int l, int r )
{
    //for(int i=1;i<=n;i++)
    //cout<<suma(1,1,n,i,i)<<" ";
    //cout<<'\n';
    return suma(1,1,n,l,r);
}

• 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