Submission #1134200

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134200		alexdd	Watering can (POI13_kon)	C++20	100 / 100	242 ms	18224 KiB

kon

#include<bits/stdc++.h>
using namespace std;
const int INF = 1e8;
int a[300005];
int aib[300005],copn;
int qry_aib(int poz)
{
    poz++;
    int aux=0;
    for(int i=poz;i>0;i-=(i&(-i)))
        aux+=aib[i];
    return aux;
}
void upd_aib(int poz, int newv)
{
    poz++;
    for(int i=poz;i<=copn;i+=(i&(-i)))
        aib[i]+=newv;
}

pair<int,int> aint[1100000];
int lazy[1100000];
void propagate(int nod)
{
    if(lazy[nod]==0)
        return;
    aint[nod*2].first += lazy[nod];
    aint[nod*2+1].first += lazy[nod];
    lazy[nod*2] += lazy[nod];
    lazy[nod*2+1] += lazy[nod];
    lazy[nod]=0;
}
void upd(int nod, int st, int dr, int le, int ri, int newv)
{
    if(le>ri)
        return;
    if(le==st && dr==ri)
    {
        aint[nod].first += newv;
        lazy[nod] += newv;
        return;
    }
    propagate(nod);
    int mij=(st+dr)/2;
    upd(nod*2,st,mij,le,min(mij,ri),newv);
    upd(nod*2+1,mij+1,dr,max(mij+1,le),ri,newv);
    aint[nod] = min(aint[nod*2], aint[nod*2+1]);
}
void build(int nod, int st, int dr)
{
    lazy[nod]=0;
    if(st==dr)
    {
        aint[nod] = {0,st};
        return;
    }
    int mij=(st+dr)/2;
    build(nod*2,st,mij);
    build(nod*2+1,mij+1,dr);
    aint[nod] = min(aint[nod*2], aint[nod*2+1]);
}
void inicjuj(int n, int k, int *D)
{
    for(int i=0;i<=n;i++)
        aib[i]=0;
    build(1,0,n-1);
    copn=n;
    for(int i=0;i<n;i++)
    {
        a[i] = k - D[i];
        if(a[i]<=0)
        {
            upd_aib(i,+1);
            upd(1,0,n-1,i,i,INF);
        }
        else
        {
            upd(1,0,n-1,i,i,a[i]);
        }
    }
}
void podlej(int le, int ri)
{
    upd(1,0,copn-1,le,ri,-1);
}
int dojrzale(int le, int ri)
{
    while(aint[1].first<=0)
    {
        upd_aib(aint[1].second, +1);
        upd(1,0,copn-1,aint[1].second,aint[1].second,INF);
    }
    return qry_aib(ri)-qry_aib(le-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: 10 / 10
• Subtask 10: 10 / 10