oj.uz

Submission #646283

# Submission time Handle Problem Language Result Execution time Memory
646283 2022-09-29T11:42:58 Z Kripton Weirdtree (RMI21_weirdtree) C++14
100 / 100
 286 ms 37196 KB 
#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.0 / 5.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 50 ms 9440 KB Output is correct
4 Correct 52 ms 9500 KB Output is correct

Subtask #3
8.0 / 8.0

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

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 280 ms 37196 KB Output is correct
4 Correct 246 ms 37184 KB Output is correct
5 Correct 286 ms 37160 KB Output is correct
6 Correct 237 ms 36992 KB Output is correct
7 Correct 9 ms 9148 KB Output is correct
8 Correct 41 ms 8948 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9148 KB Output is correct
2 Correct 41 ms 8948 KB Output is correct
3 Correct 103 ms 35644 KB Output is correct
4 Correct 106 ms 35956 KB Output is correct

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 50 ms 9440 KB Output is correct
4 Correct 52 ms 9500 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 9 ms 9148 KB Output is correct
8 Correct 41 ms 8948 KB Output is correct
9 Correct 45 ms 9504 KB Output is correct
10 Correct 48 ms 9412 KB Output is correct
11 Correct 44 ms 9488 KB Output is correct
12 Correct 63 ms 9564 KB Output is correct
13 Correct 51 ms 9480 KB Output is correct

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 50 ms 9440 KB Output is correct
4 Correct 52 ms 9500 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 280 ms 37196 KB Output is correct
8 Correct 246 ms 37184 KB Output is correct
9 Correct 286 ms 37160 KB Output is correct
10 Correct 237 ms 36992 KB Output is correct
11 Correct 103 ms 35644 KB Output is correct
12 Correct 106 ms 35956 KB Output is correct
13 Correct 45 ms 9504 KB Output is correct
14 Correct 48 ms 9412 KB Output is correct
15 Correct 44 ms 9488 KB Output is correct
16 Correct 63 ms 9564 KB Output is correct
17 Correct 51 ms 9480 KB Output is correct
18 Correct 9 ms 9148 KB Output is correct
19 Correct 41 ms 8948 KB Output is correct
20 Correct 210 ms 36248 KB Output is correct
21 Correct 233 ms 36752 KB Output is correct
22 Correct 221 ms 36580 KB Output is correct
23 Correct 242 ms 36604 KB Output is correct
24 Correct 216 ms 36416 KB Output is correct