oj.uz

Submission #78001

# Submission time Handle Problem Language Result Execution time Memory
78001 2018-10-01T17:39:27 Z carolang Growing Trees (BOI11_grow) C++14
0 / 100
 1000 ms 5412 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 cantidadTotal;
    	
    	void init(int c, vector<tint> &v){
    		cantidadTotal = 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){
    		i += N;
    		j += N;
    		while(i != j){
				if(i%2 == 1){
					valores[i]++;
					i++;
				}
				if(j%2 == 1){
					j--;
					valores[j]++;
				}
				i/=2;
				j/=2;
			}
    	}
    	
    	int lower_bound(tint x){
    		int ini = -1;
    		int fin = cantidadTotal;
    		while(fin - ini > 1){
    			int prom = (ini + fin) / 2;
    			if(hallarValor(prom) < x){
    				ini = prom;
    			} else {
    				fin = prom;
    			}
    		}
    		return fin;
    	}
    	int upper_bound(tint x){
    		int ini = -1;
    		int fin = cantidadTotal;
    		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 == cantidadTotal) return;
    		cant = min(cant, cantidadTotal - pIni);
    		
    		int pFin = min(pIni + cant, cantidadTotal);
    		tint 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);
    	}
    	
    	void imprimir(){
			forn(i, cantidadTotal){
				cerr << hallarValor(i) << " ";
			}cerr << endl;
		}
    };
     
    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){
			gt.imprimir();
    		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 1077 ms 4472 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1078 ms 4472 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 1068 ms 4472 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 1065 ms 4552 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 1067 ms 4552 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 1081 ms 4552 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 1072 ms 5316 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 1082 ms 5316 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 1063 ms 5412 KB Time limit exceeded