#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;
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
228 ms |
3832 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
275 ms |
4164 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
281 ms |
5144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
201 ms |
6308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
203 ms |
6676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
219 ms |
7324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
289 ms |
8472 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
278 ms |
9264 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
378 ms |
9924 KB |
Output isn't correct |
