#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){
if(i == j){
return;
}
if(i%2 == 1){
valores[i]++;
i++;
}
if(j%2 == 1){
j--;
valores[j]++;
}
incrementarRango(i/2, j/2);
}
int lower_bound(int 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(int 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);
int 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);
}
};
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;
actualizar(hi, ci);
} else {
tint hMin, hMax;
cin >> hMin, hMax;
cout << hallarCantidad(hMin, hMax) << endl;
}
}
}
Compilation message
grow.cpp: In function 'int main()':
grow.cpp:111:10: error: 'M' was not declared in this scope
forn(i, M){
^
grow.cpp:8:45: note: in definition of macro 'forsn'
#define forsn(i,s,n) for(int i=(s); i<(int)(n); i++)
^
grow.cpp:111:2: note: in expansion of macro 'forn'
forn(i, M){
^~~~
grow.cpp:117:4: error: 'actualizar' was not declared in this scope
actualizar(hi, ci);
^~~~~~~~~~
grow.cpp:120:21: warning: right operand of comma operator has no effect [-Wunused-value]
cin >> hMin, hMax;
^
grow.cpp:121:12: error: 'hallarCantidad' was not declared in this scope
cout << hallarCantidad(hMin, hMax) << endl;
^~~~~~~~~~~~~~
