oj.uz

Submission #78002

# Submission time Handle Problem Language Result Execution time Memory
78002 2018-10-01T17:42:16 Z carolang Growing Trees (BOI11_grow) C++14
100 / 100
 380 ms 29664 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){
    		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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 3320 KB Output is correct
2 Correct 286 ms 5120 KB Output is correct
3 Correct 226 ms 6608 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6608 KB Output is correct
2 Correct 13 ms 6608 KB Output is correct
3 Correct 14 ms 6608 KB Output is correct
4 Correct 10 ms 6608 KB Output is correct
5 Correct 217 ms 7024 KB Output is correct
6 Correct 277 ms 8248 KB Output is correct
7 Correct 22 ms 8248 KB Output is correct
8 Correct 254 ms 8680 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 8996 KB Output is correct
2 Correct 266 ms 9948 KB Output is correct
3 Correct 7 ms 9948 KB Output is correct
4 Correct 250 ms 10700 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 10812 KB Output is correct
2 Correct 278 ms 11864 KB Output is correct
3 Correct 17 ms 11864 KB Output is correct
4 Correct 259 ms 13004 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 13176 KB Output is correct
2 Correct 265 ms 14472 KB Output is correct
3 Correct 87 ms 14472 KB Output is correct
4 Correct 174 ms 16016 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 16140 KB Output is correct
2 Correct 305 ms 17476 KB Output is correct
3 Correct 217 ms 19068 KB Output is correct
4 Correct 70 ms 19068 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 19732 KB Output is correct
2 Correct 240 ms 20820 KB Output is correct
3 Correct 236 ms 22232 KB Output is correct
4 Correct 65 ms 22232 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 22856 KB Output is correct
2 Correct 268 ms 23912 KB Output is correct
3 Correct 77 ms 24540 KB Output is correct
4 Correct 256 ms 25776 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 25860 KB Output is correct
2 Correct 298 ms 27240 KB Output is correct
3 Correct 262 ms 29084 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 380 ms 29664 KB Output is correct