#include <algorithm>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> pipii;
typedef vector<vector<ll>> matrix;
const int RAGETREE_SZ = 100005;
int n;
// max value in subinterval
int ragetree[4 * RAGETREE_SZ];
int ragetreelazy[4 * RAGETREE_SZ];
void pushdown(int idx) {
ragetreelazy[2*idx] += ragetreelazy[idx];
ragetreelazy[2*idx+1] += ragetreelazy[idx];
ragetreelazy[idx] = 0;
}
void pullup(int idx) {
ragetree[idx] = max(ragetree[2*idx] + ragetreelazy[2*idx], ragetree[2*idx+1] + ragetreelazy[2*idx+1]);
}
void inc(int idx, int lhs, int rhs, int a, int b) {
if(lhs >= a && rhs <= b) {
ragetreelazy[idx]++;
return;
}
pushdown(idx);
int mid = (lhs+rhs)/2;
if(mid >= a) inc(2*idx, lhs, mid, a, b);
if(mid+1 <= b) inc(2*idx+1, mid+1, rhs, a, b);
pullup(idx);
}
// increment everything in indices [lhs, rhs] by 1
void inc(int lhs, int rhs) {
inc(1, 0, n-1, lhs, rhs);
}
int get(int idx, int lhs, int rhs, int i) {
if(lhs == rhs) return ragetree[idx] + ragetreelazy[idx];
pushdown(idx);
int ret = -1;
int mid = (lhs+rhs)/2;
if(i <= mid) ret = get(2*idx, lhs, mid, i);
else ret = get(2*idx+1, mid+1, rhs, i);
assert(ret >= 0);
pullup(idx);
return ret;
}
// return ith entry
int get(int i) {
return get(1, 0, n-1, i);
}
int get_le_count(int idx, int lhs, int rhs, int v) {
// this probably needs ragetreemin
if(ragetree[idx] + ragetreelazy[idx] <= v) return rhs;
if(lhs == rhs) return -1;
pushdown(idx);
int ret = -1;
int mid = (lhs+rhs)/2;
if(ragetree[2*idx]+ragetreelazy[2*idx] <= v) {
ret = max(mid, get_le_count(2*idx+1, mid+1, rhs, v));
}
else {
ret = get_le_count(2*idx, lhs, mid, v);
}
pullup(idx);
return ret;
}
// return largest index <= v, -1 if none exists
int get_le_idx(int v) {
int ret = get_le_count(1, 0, n-1, v);
// cout << "largest index <= " << v << " is apparently " << ret << endl;
return ret;
}
int get_ge_count(int idx, int lhs, int rhs, int v) {
if(ragetree[idx] + ragetreelazy[idx] < v) return n;
if(lhs == rhs) return lhs;
pushdown(idx);
int ret = n;
int mid = (lhs+rhs)/2;
if(ragetree[2*idx] + ragetreelazy[2*idx] >= v) {
ret = get_ge_count(2*idx, lhs, mid, v);
}
else {
ret = get_ge_count(2*idx+1, mid+1, rhs, v);
}
pullup(idx);
return ret;
}
// return smallest index >= v, RAGETREE_SZ if none exists
int get_ge_idx(int v) {
return get_ge_count(1, 0, n-1, v);
}
void init(int idx, int lhs, int rhs, vector<int>& v) {
if(lhs >= v.size()) return;
if(lhs == rhs) {
ragetree[idx] = v[lhs];
}
else {
int mid = (lhs+rhs)/2;
init(2*idx, lhs, mid, v);
init(2*idx+1, mid+1, rhs, v);
pullup(idx);
}
}
void init(vector<int>& v) {
init(1, 0, n-1, v);
}
// increase the k smallest things >= h
void update(int k, int h) {
// cout << "processing " << k << " " << h << endl;
int lhs = get_ge_idx(h);
if(lhs == n) return;
int lowestH = get(lhs);
// cout << "lowest at this point is " << lhs << " index with height " << lowestH << endl;
int largestH = get(min(n-1, lhs + k-1));
// cout << "largest height that will be affected is " << largestH << endl;
int rhs = get_le_idx(largestH);
if(lowestH < largestH) {
// increment everything less
int nrhs = get_le_idx(largestH-1);
// cout << "small increment interval is " << lhs << " " << rhs << endl;
assert(lhs <= nrhs);
assert(nrhs - lhs + 1 <= k);
inc(lhs, nrhs);
k -= nrhs-lhs+1;
}
// increment the largest largestH values
// cout << "still need to increment " << k << " at height " << largestH << endl;
// cout << "largest index for this is " << rhs << endl;
int nlhs = rhs-k+1;
assert(nlhs >= lhs);
inc(nlhs, rhs);
}
int query(int lhs, int rhs) {
return get_le_idx(rhs) - get_le_idx(lhs-1);
}
void solve() {
int m;
cin >> n >> m;
vector<int> v;
v.resize(n);
for(int i = 0; i < n; i++) cin >> v[i];
sort(v.begin(), v.end());
init(v);
while(m--) {
string s;
cin >> s;
if(s == "F") {
int k, h;
cin >> k >> h;
update(k, h);
}
else {
int lhs, rhs;
cin >> lhs >> rhs;
cout << query(lhs, rhs) << "\n";
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
/*
int t;
cin >> t;
for(int i = 1; i <= t; i++) {
cout << "Case #" << i << ": ";
solve();
}
*/
solve();
}
Compilation message
grow.cpp: In function 'void init(int, int, int, std::vector<int>&)':
grow.cpp:107:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(lhs >= v.size()) return;
~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
23 ms |
5752 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
384 KB |
Output is correct |
| 2 |
Correct |
6 ms |
512 KB |
Output is correct |
| 3 |
Runtime error |
5 ms |
896 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
18 ms |
1280 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
996 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
23 ms |
3648 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
18 ms |
5176 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16 ms |
4480 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
20 ms |
5260 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
25 ms |
5880 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
29 ms |
6392 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
