# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
197600 | stefdasca | Watering can (POI13_kon) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#include "koninc.h"
using namespace std;
const int MAXN = 300001;
int N, K, v[MAXN+5];
struct nod
{
int mn, cnt;
int lazy;
};
nod aint[MAXN * 4 + 5];
void solve_lazy(int nod)
{
if(2 * nod + 1 <= 4 * n)
{
aint[2 * nod].lazy += aint[nod].lazy;
aint[2 * nod + 1].lazy += aint[nod].lazy;
}
aint[nod].lazy = 0;
}
void build(int nod, int left, int right)
{
if(left == right)
{
aint[nod].mn = K - v[left];
if(aint[nod].mn <= 0)
aint[nod] = {INF, 1, 0};
return;
}
int mid = (left + right) / 2;
build(2 * nod, left, mid);
build(2 * nod + 1, mid + 1, right);
aint[nod].cnt = aint[2 * nod].cnt + aint[2 * nod + 1].cnt;
aint[nod].mn = min(aint[2 * nod].mn + aint[2 * nod].lazy, aint[2 * nod + 1].mn + aint[2 * nod + 1].lazy);
}
void update(int nod, int left, int right, int l, int r)
{
if(l <= left && right <= r && aint[nod].mn + aint[nod].lazy - 1 > 0)
{
aint[nod].lazy--;
return ;
}
if(left == right)
{
aint[nod] = {(1<<30), 1, 0};
return ;
}
solve_lazy(nod);
int mid = (left + right) / 2;
if(l <= mid)
update(2 * nod, left, mid, l, r);
if(mid < r)
update(2 * nod + 1, mid + 1, right, l, r);
aint[nod].cnt = aint[2 * nod].cnt + aint[2 * nod + 1].cnt;
aint[nod].mn = min(aint[2 * nod].mn + aint[2 * nod].lazy, aint[2 * nod + 1].mn + aint[2 * nod + 1].lazy);
}
int query(int nod, int left, int right, int l, int r)
{
if(l <= left && right <= r)
return aint[nod].cnt;
int mid = (left + right) / 2;
int ans = 0;
if(l <= mid)
ans += query(2 * nod, left, mid, l, r);
if(mid < r)
ans += query(2 * nod + 1, mid + 1, right, l, r);
return ans;
}
void inicjuj(int n, int k, int *D)
{
N = n, K = k;
for(int i = 1; i <= n; ++i)
v[i] = D[i-1];
build(1, 1, n);
}
void podlej(int a, int b)
{
++a, ++b;
upd(1, 1, n, a, b);
}
int dojrzale(int a, int b)
{
++a, ++b;
return query(1, 1, n, a, b);
}