# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
482106 | MilosMilutinovic | 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>
#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define pb push_back
#define gas INT_MAX
using namespace std;
int N,K;
int niz[300005];
int mn[1000005];
int cnt[1000005];
int lzy[1000005];
void upd(int node){
cnt[node] = cnt[node * 2] + cnt[node * 2 + 1];
mn[node] = min(mn[node * 2], mn[node * 2 + 1]);
}
void build(int node, int l, int r){
if(l == r){
if(niz[l] > 0)mn[node] = niz[l];
else{
cnt[node] = 1;
mn[node] = 1e9;
}
return;
}
int mid = (l + r) / 2;
build(node * 2, l, mid);
build(node * 2 + 1, mid + 1, r);
upd(node);
}
void propagate(int node){
if(mn[node] != 1e9)mn[node] -= lzy[node];
lzy[node * 2] += lzy[node];
lzy[node * 2 + 1] += lzy[node];
lzy[node] = 0;
}
void update(int node, int l, int r, int ll, int rr, int x){
if(l > r || l > rr || r < ll)return;
if(ll <= l && r <= rr){
lzy[node] += x;
propagate(node);
return;
}
propagate(node);
int mid = (l + r) / 2;
update(node * 2, l, mid, ll, rr, x);
update(node * 2 + 1, mid + 1, r, ll, rr, x);
upd(node);
}
int get(int node, int l, int r, int ll, int rr){
propagate(node);
if(l > r || l > rr || r < ll)return 0;
if(ll <= l && r <= rr)return cnt[node];
int mid = (l + r) / 2;
return get(node * 2, l, mid, ll, rr) + get(node * 2 + 1, mid + 1, r, ll, rr);
}
void rebuild(int node, int l, int r){
propagate(node);
if(mn[node] > 0)return;
if(l == r){
mn[node] = 1e9;
cnt[node] = 1;
return;
}
int mid = (l + r) / 2;
rebuild(node * 2, l, mid);
rebuild(node * 2 + 1, mid + 1, r);
upd(node);
}
void inicjuj(int n, int k, int *D)
{
N = n;
K = k;
ff(i,1,n)niz[i] = k-D[i-1];
build(1, 1, N);
}
void podlej(int a, int b)
{
a++;
b++;
update(1, 1, N, a, b, 1);
rebuild(1, 1, N);
}
int dojrzale(int a, int b)
{
a++;
b++;
return get(1, 1, N, a, b);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, k;
cin >> n >> k;
int d[n];
ff(i,0,n-1)cin >> d[i];
inicjuj(n, k, d);
cout << dojrzale(2, 3) << "\n";
podlej(0, 2);
cout << dojrzale(1, 2) << "\n";
podlej(2, 3);
podlej(0, 1);
cout << dojrzale(0, 3) << "\n";
return 0;
}