Submission #1203777

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203777		vicvic	Watering can (POI13_kon)	C++20	0 / 100	29 ms	16708 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;
    }
    int 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]);
        }
    }
    int 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)
{
    x++;
    for (int i=x;i<=n;i+=(i&-i))
        aib[i]+=val;
}
int queryAib (int x)
{
    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 (0, n-1);
    for (int i=0;i<n;i++)
    {
        a[i]=k-d[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)
{
    aint.update (st, dr, -1);
}
int dojrzale (int st, int 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);
}

Compilation message (stderr)

kon.cpp: In member function 'int SegTree::actbuild(int, int, int)':
kon.cpp:31:5: warning: no return statement in function returning non-void [-Wreturn-type]
   31 |     }
      |     ^
kon.cpp: In member function 'int SegTree::build(int, int)':
kon.cpp:37:5: warning: no return statement in function returning non-void [-Wreturn-type]
   37 |     }
      |     ^

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