FIRS - Hàng cây
Tác giả: khuc_tuan
Ngôn ngữ: C++
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <sstream>
#include <cstdlib>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
using namespace std;
#define Rep(i,n) for(int i=0,lll=(n);i<lll;++i)
#define For(i,a,b) for(int i=(a),lll=(b);i<=lll;++i)
#define Ford(i,a,b) for(int i=(a),lll=(b);i>=lll;--i)
#define pb push_back
#define MP make_pair
#define fi first
#define se second
#define nextint __nextint()
inline int __nextint() { int x; scanf("%d", &x); return x; }
const int MAXN = 100010;
int n;
int a[MAXN];
int mm[MAXN * 4];
// bool mark[MAXN];
void init(int n, int l, int r) {
if(l==r) {
// cout << l << " " << a[l] << " day " << endl;
mm[n] = a[l];
return;
}
else {
int m = (l+r) / 2;
init(2 *n, l,m );
init(2*n+1,m+1,r);
mm[n] = min(mm[n*2], mm[n*2+1]);
}
}
int findmin(int n, int l, int r) {
// cout << "find min " << n << " " << l << " " << r << endl;
if(l==r) return l;
int m = (l+r) / 2;
if(mm[n] == mm[2*n]) return findmin(2*n,l,m);
else return findmin(2*n+1,m+1,r);
}
int getvalue(int n,int l, int r, int pos) {
if(l==r) return mm[n];
else {
int m = (l+r) / 2;
if(pos <= m) return getvalue( 2 * n, l, m, pos);
else return getvalue( 2 * n + 1, m +1, r, pos);
}
}
void update(int n, int l, int r, int pos, int val) {
if(l==r) {
mm[n] = val;
return;
}
else {
int m = (l+r) / 2;
if(pos <= m) update( 2 * n, l, m, pos, val);
if(m < pos) update(2*n+1,m+1,r,pos,val);
mm[n] = min(mm[n*2], mm[n*2+1]);
}
}
int main() {
scanf("%d", &n);
Rep(i,n) scanf("%d", a+i);
init(1,0,n-1);
//cout << mm[1] << " " << mm[2] << " " << mm[3] << endl;
int ngay = 0;
while(true) {
int pos = findmin( 1, 0, n-1);
int value = getvalue( 1, 0, n-1, pos);
// printf("%d %d\n", pos, value);
if(value >= 1000000) break;
else {
++ngay;
update( 1, 0, n-1, pos, 1000000);
if(pos > 0) update( 1, 0, n-1, pos - 1, 1000000);
if(pos + 1 < n) update( 1, 0, n-1, pos + 1, 1000000);
}
}
printf("%d\n", ngay);
return 0;
}