oj.uz

Submission #500796

# Submission time Handle Problem Language Result Execution time Memory
500796 2022-01-01T09:42:49 Z andrei_boaca Weirdtree (RMI21_weirdtree) C++17
10 / 100
 2000 ms 44176 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];
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;
    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)
{
    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;
        }
}
void cutupd(int nod,int st,int dr,int a,int b,int val,int extra)
{
    if(st!=dr&&arb[nod].lazy!=0)
        prop(nod);
    arb[nod].lazy=0;
    int mij=(st+dr)/2;
    date x=arb[nod];
    if(st>=a&&dr<=b)
    {
        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;
            return;
        }
        if(x.max1-val>x.max2&&extra==0)
        {
            arb[nod].max1-=val;
            arb[nod].lazy+=val;
            arb[nod].suma-=val*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)
        cutupd(nod*2,st,mij,a,b,val,extra);
    if(b>mij)
        cutupd(nod*2+1,mij+1,dr,a,b,val,extra);
    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&&arb[nod].lazy!=0)
        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;
        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;
        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;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2081 ms 332 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2081 ms 332 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 44160 KB Output is correct
2 Correct 168 ms 44176 KB Output is correct
3 Correct 22 ms 10828 KB Output is correct
4 Correct 44 ms 10948 KB Output is correct

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -