# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1134047 | alexdd | Watering can (POI13_kon) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
int a[300005],aib[3000015];
int qry(int poz)
{
poz+=2;
int aux=0;
for(int i=poz;i>0;i-=(i&(-i)))
aux+=aib[i];
return aux;
}
void upd(int poz, int newv)
{
poz+=2;
for(int i=poz;i<=n+2;i+=(i&(-i)))
aib[i]+=newv;
}
void inicjuj(int n, int k, int *D)
{
for(int i=0;i<=n+3;i++)
aib[i]=0;
for(int i=0;i<n;i++)
{
a[i] = max(0, k - D[i]);
if(a[i]==0) upd(i,+1);
}
}
void podlej(int le, int ri)
{
for(int i=le;i<=ri;i++)
{
a[i]--;
if(a[i]==0) upd(i,+1);
}
}
int dojrzale(int le, int ri)
{
return qry(ri) - qry(le-1);
}