Submission #78002

#	Time	Username	Problem	Language	Result	Execution time	Memory
78002		carolang	Growing Trees (BOI11_grow)	C++14	100 / 100	380 ms	29664 KiB

grow

    #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){
    		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: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10