oj.uz

Submission #500834

# Submission time Handle Problem Language Result Execution time Memory
500834 2022-01-01T11:34:07 Z andrei_boaca Weirdtree (RMI21_weirdtree) C++17
100 / 100
 956 ms 45036 KB 
#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

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.0 / 5.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 125 ms 11324 KB Output is correct
4 Correct 151 ms 11316 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 332 KB Output is correct
2 Correct 7 ms 432 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 332 KB Output is correct
2 Correct 7 ms 432 KB Output is correct
3 Correct 956 ms 45036 KB Output is correct
4 Correct 826 ms 44916 KB Output is correct
5 Correct 873 ms 44980 KB Output is correct
6 Correct 803 ms 44872 KB Output is correct
7 Correct 28 ms 10828 KB Output is correct
8 Correct 70 ms 10952 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 10828 KB Output is correct
2 Correct 70 ms 10952 KB Output is correct
3 Correct 172 ms 44180 KB Output is correct
4 Correct 193 ms 44232 KB Output is correct

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 125 ms 11324 KB Output is correct
4 Correct 151 ms 11316 KB Output is correct
5 Correct 4 ms 332 KB Output is correct
6 Correct 7 ms 432 KB Output is correct
7 Correct 28 ms 10828 KB Output is correct
8 Correct 70 ms 10952 KB Output is correct
9 Correct 128 ms 11316 KB Output is correct
10 Correct 131 ms 11376 KB Output is correct
11 Correct 146 ms 11324 KB Output is correct
12 Correct 132 ms 11388 KB Output is correct
13 Correct 136 ms 11388 KB Output is correct

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 125 ms 11324 KB Output is correct
4 Correct 151 ms 11316 KB Output is correct
5 Correct 4 ms 332 KB Output is correct
6 Correct 7 ms 432 KB Output is correct
7 Correct 956 ms 45036 KB Output is correct
8 Correct 826 ms 44916 KB Output is correct
9 Correct 873 ms 44980 KB Output is correct
10 Correct 803 ms 44872 KB Output is correct
11 Correct 172 ms 44180 KB Output is correct
12 Correct 193 ms 44232 KB Output is correct
13 Correct 128 ms 11316 KB Output is correct
14 Correct 131 ms 11376 KB Output is correct
15 Correct 146 ms 11324 KB Output is correct
16 Correct 132 ms 11388 KB Output is correct
17 Correct 136 ms 11388 KB Output is correct
18 Correct 28 ms 10828 KB Output is correct
19 Correct 70 ms 10952 KB Output is correct
20 Correct 605 ms 44024 KB Output is correct
21 Correct 658 ms 44132 KB Output is correct
22 Correct 610 ms 44052 KB Output is correct
23 Correct 652 ms 44112 KB Output is correct
24 Correct 621 ms 44064 KB Output is correct