#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
const ll NMAX = 100002;
const ll INF = (1LL << 60);
const ll nrbits = 20;
const int MOD = 998244353;
const int bucket = 320;
int v[NMAX];
class AINT{
public:
int aint[NMAX * 4], lazy[NMAX * 4], mini[NMAX * 4];
void init(){
for(int i = 0; i < NMAX * 4; i++){
aint[i] = lazy[i] = 0;
mini[i] = 2e9;
}
}
void build(int node, int st, int dr){
if(st == dr){
mini[node] = 0;
return;
}
int mid = (st + dr) / 2;
build(node * 2, st, mid);
build(node * 2 + 1, mid + 1, dr);
mini[node] = 0;
}
void propaga(int node, int st, int dr){
if(st != dr){
lazy[node * 2] += lazy[node];
lazy[node * 2 + 1] += lazy[node];
}
aint[node] += lazy[node];
mini[node] += lazy[node];
lazy[node] = 0;
}
void update(int node, int st, int dr, int a, int b, int val){
propaga(node, st, dr);
if(a <= st && dr <= b){
lazy[node] += val;
return;
}
int mid = (st + dr) / 2;
if(a <= mid){
update(node * 2, st, mid, a, b, val);
}
if(b > mid){
update(node * 2 + 1, mid + 1, dr, a, b, val);
}
propaga(node * 2, st, mid);
propaga(node * 2 + 1, mid + 1, dr);
aint[node] = max(aint[node * 2], aint[node * 2 + 1]);
mini[node] = min(mini[node * 2], mini[node * 2 + 1]);
}
int get(int node, int st, int dr, int a){
propaga(node, st, dr);
if(st == dr)
return aint[node];
int mid = (st + dr) / 2;
if(a <= mid){
return get(node * 2, st, mid, a);
}
return get(node * 2 + 1, mid + 1, dr, a);
}
int first(int node, int st, int dr, int a){
propaga(node, st, dr);
if(st == dr)
return st;
int mid = (st + dr) / 2;
propaga(node * 2, st, mid);
propaga(node * 2 + 1, mid + 1, dr);
if(aint[node * 2] >= a)
return first(node * 2, st, mid, a);
return first(node * 2 + 1, mid + 1, dr, a);
}
int last(int node, int st, int dr, int a){
propaga(node, st, dr);
if(st == dr)
return st;
int mid = (st + dr) / 2;
propaga(node * 2, st, mid);
propaga(node * 2 + 1, mid + 1, dr);
if(mini[node * 2 + 1] <= a)
return last(node * 2 + 1, mid + 1, dr, a);
return last(node * 2, st, mid, a);
}
}st;
int main() {
#ifdef HOME
ifstream cin(".in");
ofstream cout(".out");
#endif // HOME
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m, i;
st.init();
cin >> n >> m;
st.build(1, 1, n);
for(i = 1; i <= n; i++){
cin >> v[i];
}
sort(v + 1, v + n + 1);
for(i = 1; i <= n; i++){
st.update(1, 1, n, i, i, v[i]);
}
for(i = 1; i <= m; i++){
char c;
int a, b;
cin >> c >> a >> b;
if(c == 'C'){
int l = st.first(1, 1, n, a);
int r = st.last(1, 1, n, b);
if(st.get(1, 1, n, 1) > b){
cout << 0 << "\n";
}else if(st.get(1, 1, n, n) < a){
cout << 0 << "\n";
}else{
cout << r - l + 1 << "\n";
}
}else{
int c = a, h = b;
int poz = st.first(1, 1, n, h);
if(poz + c - 1 >= n){
st.update(1, 1, n, poz, n, 1);
}else{
int am = st.get(1, 1, n, poz + c - 1);
int maxi = st.first(1, 1, n, am);
if(maxi - 1 >= poz){
st.update(1, 1, n, poz, maxi - 1, 1);
c -= (maxi - poz);
}
int ultim = st.last(1, 1, n, am);
st.update(1, 1, n, ultim - c + 1, ultim, 1);
}
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
84 ms |
6556 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4952 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5212 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5212 KB |
Output is correct |
| 4 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 5 |
Correct |
39 ms |
6016 KB |
Output is correct |
| 6 |
Incorrect |
50 ms |
6508 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
6584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
6480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
69 ms |
6484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
91 ms |
6500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
74 ms |
6340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
112 ms |
7240 KB |
Output is correct |
| 2 |
Incorrect |
102 ms |
6740 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
96 ms |
6848 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
100 ms |
7812 KB |
Output is correct |
