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;
}

Download