답안 #500809

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
500809 2022-01-01T10:18:43 Z andrei_boaca Weirdtree (RMI21_weirdtree) C++17
컴파일 오류
0 ms 0 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)
{
    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];
    bool kk=0;
    if(x.max1==997825028)
        kk=1;
    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)
        {
            bool ok=0;
            if(x.max1==997949551)
                ok=1;
            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&&arb[nod*2].max1>=need)
        cutupd(nod*2,st,mij,a,b,val,extra);
    if(b>mij&&arb[nod*2+1].max1>=need)
        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);
        bool ok=0;
        if(x.max2==997825028)
            ok=1;
        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;
        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, int, int)':
weirdtree.cpp:84:18: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
   84 |             bool ok=0;
      |                  ^~
weirdtree.cpp:65:10: warning: variable 'kk' set but not used [-Wunused-but-set-variable]
   65 |     bool kk=0;
      |          ^~
weirdtree.cpp: In function 'void cut(int, int, int)':
weirdtree.cpp:172:14: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
  172 |         bool ok=0;
      |              ^~
/usr/bin/ld: /tmp/cc44YKju.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cchQoecx.o:weirdtree.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status