Submission #500834

#	Time	Username	Problem	Language	Result	Execution time	Memory
500834		andrei_boaca	Weirdtree (RMI21_weirdtree)	C++17	100 / 100	956 ms	45036 KiB

weirdtree

#include <bits/stdc++.h>
#include "weirdtree.h"
//#include "grader.cpp"
using namespace std;
typedef long long ll;
int n;
struct date
{
    ll max1,max2,fr1,suma,lazy;
} arb[1500005];
ll need=0;
void build(int nod,int st,int dr)
{
    arb[nod].fr1=dr-st+1;
    arb[nod].max1=0;
    arb[nod].max2=0;
    arb[nod].suma=0;
    arb[nod].lazy=0;
    if(st==dr)
        return;
    int mij=(st+dr)/2;
    build(nod*2,st,mij);
    build(nod*2+1,mij+1,dr);
}
date combine(date a, date b)
{
    date rez={0,0,0,0,0};
    rez.suma=(a.suma+b.suma);
    rez.max1=max(a.max1,b.max1);
    if(a.max1==b.max1)
    {
        rez.fr1=a.fr1+b.fr1;
        rez.max2=max(a.max2,b.max2);
    }
    else if(a.max1>b.max1)
    {
        rez.fr1=a.fr1;
        rez.max2=max(a.max2,b.max1);
    }
    else if(a.max1<b.max1)
    {
        rez.fr1=b.fr1;
        rez.max2=max(a.max1,b.max2);
    }
    return rez;
}
void prop(int nod)
{
    assert(arb[nod].max1>=arb[nod].max2);
    int val=arb[nod].lazy;
    for(int i=nod*2;i<=nod*2+1;i++)
        if(arb[i].max1-val==arb[nod].max1)
        {
            arb[i].max1-=val;
            arb[i].lazy+=val;
            arb[i].suma-=val*arb[i].fr1;
            assert(arb[i].max1>arb[i].max2||(arb[i].max1==0));
        }
}
ll lft;
void cutupd(int nod,int st,int dr,int a,int b,ll val,int extra)
{
    if(st!=dr)
        prop(nod);
    arb[nod].lazy=0;
    int mij=(st+dr)/2;
    date x=arb[nod];
    ll aux=extra;
    if(st>=a&&dr<=b&&arb[nod].max1==need)
    {
        if(extra>=x.fr1)
        {
            val++;
            extra=0;
        }
        if(st==dr)
        {
            arb[nod].max1=max(arb[nod].max1-val,0LL);
            arb[nod].suma=arb[nod].max1;
            arb[nod].fr1=1;
            lft=max(0LL,lft-1);
            return;
        }
        if(x.max1-val>x.max2&&extra==0)
        {
            arb[nod].max1-=val;
            arb[nod].lazy+=val;
            arb[nod].suma-=1LL*val*arb[nod].fr1;
            lft=max(0LL,lft-arb[nod].fr1);
            return;
        }
        else if(x.max1-val==x.max2&&extra==0)
        {
            if(arb[nod*2].max1==x.max1)
                cutupd(nod*2,st,mij,a,b,val,extra);
            if(arb[nod*2+1].max1==x.max1)
                cutupd(nod*2+1,mij+1,dr,a,b,val,extra);
            arb[nod]=combine(arb[nod*2],arb[nod*2+1]);
            return;
        }
        if(arb[nod*2].max1==x.max1)
        {
            int put=min(extra*1LL,arb[nod*2].fr1);
            cutupd(nod*2,st,mij,a,b,val,put);
            if(arb[nod*2+1].max1==x.max1)
                cutupd(nod*2+1,mij+1,dr,a,b,val,extra-put);
            arb[nod]=combine(arb[nod*2],arb[nod*2+1]);
            return;
        }
        cutupd(nod*2+1,mij+1,dr,a,b,val,extra);
        arb[nod]=combine(arb[nod*2],arb[nod*2+1]);
        return;
    }
    if(a<=mij&&arb[nod*2].max1>=need)
        cutupd(nod*2,st,mij,a,b,val,lft);
    if(b>mij&&arb[nod*2+1].max1>=need)
        cutupd(nod*2+1,mij+1,dr,a,b,val,lft);
    arb[nod]=combine(arb[nod*2],arb[nod*2+1]);
}
void magicupd(int nod,int st,int dr,int poz,int val)
{
    if(st!=dr&&arb[nod].lazy!=0)
        prop(nod);
    arb[nod].lazy=0;
    if(st==poz&&dr==poz)
    {
        arb[nod].suma=val;
        arb[nod].max1=val;
        arb[nod].fr1=1;
        arb[nod].max2=0;
        arb[nod].lazy=0;
        return;
    }
    int mij=(st+dr)/2;
    if(poz<=mij)
        magicupd(nod*2,st,mij,poz,val);
    if(poz>mij)
        magicupd(nod*2+1,mij+1,dr,poz,val);
    arb[nod]=combine(arb[nod*2],arb[nod*2+1]);
}
date query(int nod,int st,int dr,int a, int b)
{
    if(st!=dr)
        prop(nod);
    arb[nod].lazy=0;
    if(st>=a&&dr<=b)
        return arb[nod];
    date rez={0,0,0,0,0};
    ll mij=(st+dr)/2;
    if(a<=mij)
    {
        date x=query(nod*2,st,mij,a,b);
        rez=combine(rez,x);
    }
    if(b>mij)
    {
        date x=query(nod*2+1,mij+1,dr,a,b);
        rez=combine(rez,x);
    }
    return rez;
}
void initialise(int N, int Q, int h[]) {
    n=N;
    build(1,1,n);
    for(int i=1;i<=n;i++)
        magicupd(1,1,n,i,h[i]);
}
void cut(int l, int r, int k) {
    while(k>0)
    {
        date x=query(1,1,n,l,r);
        ll fr1=x.fr1;
        ll max1=x.max1;
        need=x.max1;
        if(max1==0)
            break;
        ll max2=x.max2;
        if((max1-max2)*fr1<=k)
        {
            cutupd(1,1,n,l,r,max1-max2,0);
            k-=(max1-max2)*fr1;
            continue;
        }
        ll val=k/fr1;
        ll extra=k%fr1;
        lft=extra;
        cutupd(1,1,n,l,r,val,extra);
        k=0;
        break;
    }
}
void magic(int i, int x) {
    magicupd(1,1,n,i,x);
}
long long int inspect(int l, int r) {
    return query(1,1,n,l,r).suma;
}

Compilation message (stderr)

weirdtree.cpp: In function 'void cutupd(int, int, int, int, int, ll, int)':
weirdtree.cpp:68:8: warning: unused variable 'aux' [-Wunused-variable]
   68 |     ll aux=extra;
      |        ^~~

• 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