oj.uz

Submission #77994

# Submission time Handle Problem Language Result Execution time Memory
77994 2018-10-01T16:39:27 Z carolang Growing Trees (BOI11_grow) C++14
0 / 100
 1000 ms 8980 KB 
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define forsn(i,s,n) for(int i=(s); i<(int)(n); i++)
#define forn(i,n) forsn(i,0,n)

typedef long long int tint;

const tint INF = 1e11;
const int N = (1<<17);


struct growingTrees{
	vector<tint> valores;
	int cantidad;
	
	void init(int c, vector<tint> &v){
		cantidad = c;
		valores = vector<tint>(2*N, 0);
		forn(i, v.size()){
			valores[N+i] = v[i];
		}
	}
	tint hallarValor(int pos){
		pos = pos + N;
		tint res = 0;
		while(pos > 0){
			res+= valores[pos];
			pos/=2;
		}
		return res;
	}
	
	void incrementarRango(int i, int j){
		if(i == j){
			return;
		}
		if(i%2 == 1){
			valores[i]++;
			i++;
		}
		if(j%2 == 1){
			j--;
			valores[j]++;
		}
		
		incrementarRango(i/2, j/2);
	}
	
	int lower_bound(int x){
		int ini = -1;
		int fin = cantidad;
		while(fin - ini > 1){
			int prom = (ini + fin) / 2;
			if(hallarValor(prom) < x){
				ini = prom;
			} else {
				fin = prom;
			}
		}
		return fin;
	}
	int upper_bound(int x){
		int ini = -1;
		int fin = cantidad;
		while(fin - ini > 1){
			int prom = (ini + fin) / 2;
			if(hallarValor(prom) <= x){
				ini = prom;
			} else {
				fin = prom;
			}
		}
		return fin;
	}
	
	void actualizar(tint hMin, int cant){
		int pIni = lower_bound(hMin);
		if(pIni == cantidad) return;
		
		int pFin = min(pIni + cant, cantidad);
		int vFin = hallarValor(pFin - 1);
		pair<int,int> lastValueRange = {lower_bound(vFin), upper_bound(vFin)};
		
		// Incrementar menores
		incrementarRango(pIni, lastValueRange.first);
		cant -= lastValueRange.first - pIni;
		
		// Incrementar iguales
		incrementarRango(lastValueRange.second - cant, lastValueRange.second);
	}
	int hallarCantidad(tint hMin, tint hMax){
		return upper_bound(hMax) - lower_bound(hMin);
	}
};

int main(){
	growingTrees gt;
	int n,m; cin >> n >> m;
	vector<tint> v(n);
	forn(i,n){
		cin >> v[i];
	}
	sort(v.begin(), v.end());
	gt.init(n, v);
	
	forn(i, m){
		char tipo; cin >> tipo;
		if(tipo == 'F'){
			int ci;
			tint hi;
			cin >> ci >> hi;
			gt.actualizar(hi, ci);
		} else {
			tint hMin, hMax;
			cin >> hMin >> hMax;
			cout << gt.hallarCantidad(hMin, hMax) << endl;
		}
	}
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1063 ms 3740 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 3740 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1068 ms 3740 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1062 ms 3740 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1073 ms 4636 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1059 ms 5260 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1077 ms 5744 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1074 ms 6524 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1070 ms 7148 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1073 ms 8980 KB Time limit exceeded