제출 #1203781

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1203781		vicvic	새로운 문제 (POI13_kon)	C++20	90 / 100	368 ms	27036 KiB

kon

#include <bits/stdc++.h>
using namespace std;
const int NMAX=3e5;
int aib[NMAX+5], n, a[NMAX+5];
class SegTree
{
public:
    pair <int, int> t[6*NMAX+5];
    int f[6*NMAX+5];
    int limst=0, limdr=0;
    void lazy (int nod)
    {
        if (f[nod]==0)
            return;
        t[nod].first+=f[nod];
        f[nod*2]+=f[nod];
        f[nod*2+1]+=f[nod];
        f[nod]=0;
    }
    void actbuild (int nod, int st, int dr)
    {
        if (st==dr)
            t[nod]={0, st};
        else
        {
            int mij = (st+dr) >> 1;
            actbuild (nod*2, st, mij);
            actbuild (nod*2+1, mij+1, dr);
            t[nod]=min (t[nod*2], t[nod*2+1]);
        }
    }
    void build (int st, int dr)
    {
        limst=st;
        limdr=dr;
        actbuild (1, limst, limdr);
    }
    void actupdate (int nod, int st, int dr, int stq, int drq, int val)
    {
        lazy (nod);
        if (stq<=st && dr<=drq)
        {
            f[nod]+=val;
            lazy (nod);
        }
        else
        {
            lazy (nod*2);
            lazy (nod*2+1);
            int mij = (st+dr) >> 1;
            if (drq<=mij)
                actupdate (nod*2, st, mij, stq, drq, val);
            else if (stq>mij)
                actupdate (nod*2+1, mij+1, dr, stq, drq, val);
            else actupdate (nod*2, st, mij, stq, drq, val), actupdate (nod*2+1, mij+1, dr, stq, drq, val);
            t[nod]=min (t[nod*2], t[nod*2+1]);
        }
    }
    void update (int st, int dr, int val)
    {
        actupdate (1, limst, limdr, st, dr, val);
    }
};
SegTree aint;
void updateAib (int x, int val)
{
    for (int i=x;i<=n;i+=(i&-i))
        aib[i]+=val;
}
int queryAib (int x)
{
    int ret=0;
    for (int i=x;i>0;i-=(i&-i))
        ret+=aib[i];
    return ret;
}
void inicjuj (int N, int k, int *d)
{
    n=N;
    for (int i=0;i<=n;i++)
        aib[i]=0;
    aint.build (1, n);
    for (int i=0;i<n;i++)
    {
        a[i+1]=k-d[i];
    }
    for (int i=1;i<=n;i++)
    {
        if (a[i]<=0)
        {
            updateAib (i, 1);
            aint.update (i, i, 1e9+1);
        }
        else
        {
            aint.update (i, i, a[i]);
        }
    }
}
void podlej (int st, int dr)
{
    st++;
    dr++;
    aint.update (st, dr, -1);
}
int dojrzale (int st, int dr)
{
    st++;
    dr++;
    while (aint.t[1].first<=0)
    {
        updateAib (aint.t[1].second, 1);
        aint.update (aint.t[1].second, aint.t[1].second, 1e9+1);
    }
    return queryAib (dr)-queryAib (st-1);
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 0 / 10
• Subtask 10: 10 / 10