oj.uz

답안 #77999

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
77999 2018-10-01T17:27:41 Z carolang Growing Trees (BOI11_grow) C++14
0 / 100
 378 ms 9924 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){
    		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 = cantidad;
    		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 = 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);
    		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, cantidad){
				cout << hallarValor(i) << " ";
			}cout << 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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 228 ms 3832 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 3832 KB Output is correct
2 Correct 12 ms 3832 KB Output is correct
3 Incorrect 13 ms 3832 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 275 ms 4164 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 281 ms 5144 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 201 ms 6308 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 203 ms 6676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 219 ms 7324 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 289 ms 8472 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 278 ms 9264 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 378 ms 9924 KB Output isn't correct