#include <iostream>
#include <bits/stdc++.h>
#define ll int
using namespace std;
const ll maxn = 2*1e5+5, INF = 1e9+9;
struct SegmentTree{
struct Node{
int sum, lz, mx;
};
int n, N;
vector<Node> T;
SegmentTree(int n) : n(n){
N = 1;
while(N < n) N*=2;
T.resize(N*2+1, {0, 0, -INF});
};
void merge(Node &n, Node a, Node b){
n.sum = a.sum+b.sum;
n.mx = max(a.mx, b.mx);
}
void upd(int i, ll x){
auto upd = [&](auto upd, int node, int low, int high, int i, ll x) -> void{
if(low == high){
T[node].sum = x;
T[node].mx = x;
return;
}
int mid = (low+high)/2;
if(i <= mid){
upd(upd, node*2, low, mid, i, x);
}else{
upd(upd, node*2+1, mid+1, high, i, x);
}
merge(T[node], T[node*2], T[node*2+1]);
};
upd(upd, 1, 1, N, i, x);
}
void down(int node, int low, int high){
int len = high-low+1;
for(int child = node*2; child <= node*2+1; child++){
if(child >= 2*N) continue;
T[child].lz += T[node].lz;
}
T[node].sum += T[node].lz*len;
T[node].mx += T[node].lz;
T[node].lz = 0;
}
void updRange(int l, int r, ll x){
if(l > r) return;
auto updRange = [&](auto updRange, int node, int low, int high, int l, int r, ll x) -> void{
if(low > r || l > high) return;
if(low >= l && r >= high){
T[node].lz += x;
down(node, low, high);
return;
}
down(node, low, high);
int mid = (low+high)/2;
updRange(updRange, node*2, low, mid, l, r, x);
updRange(updRange, node*2+1, mid+1, high, l, r, x);
merge(T[node], T[node*2], T[node*2+1]);
};
updRange(updRange, 1, 1, N, l, r, x);
}
int walkMax(int l, int r, int dir, ll x){
auto walkMax = [&](auto walkMax, int node, int low, int high, int l, int r, int dir, ll x) -> int{
if(low > r || l > high){
return -1;
}
down(node, low, high);
if(T[node].mx < x){
return -1;
}
if(low == high) return low;
int mid = (low+high)/2;
int left = walkMax(walkMax, node*2, low, mid, l, r, dir, x);
int right = walkMax(walkMax, node*2+1, mid+1, high, l, r, dir, x);
if(dir == 0){
if(left != -1) return left;
return right;
}else{
if(right != -1) return right;
return left;
}
};
return walkMax(walkMax, 1, 1, N, l, r, dir, x);
}
ll getSum(int l, int r){
if(l > r) return 0;
auto getSum = [&](auto getSum, int node, int low, int high, int l, int r) -> ll{
if(low > r || l > high) return 0;
if(low >= l && r >= high){
down(node, low, high);
return T[node].sum;
}
down(node, low, high);
int mid = (low+high)/2;
return getSum(getSum, node*2, low, mid, l, r)+getSum(getSum, node*2+1, mid+1, high, l, r);
};
return getSum(getSum, 1, 1, N, l, r);
}
};
void solve(){
int n, Q;
cin >> n >> Q;
vector<ll> a(n+1);
for(int i = 1; i <= n; i++){
cin >> a[i];
}
sort(a.begin()+1, a.end());
SegmentTree T(n+5);
for(int i = 1; i <= n; i++){
T.upd(i, a[i]);
}
for(int i = 1; i <= Q; i++){
char t;
ll c, h, low, high;
cin >> t;
if(t == 'F'){
cin >> c >> h;
int l = T.walkMax(1, n, 0, h);
int r = l+c-1;
r = min(r, n);
ll x = T.getSum(r, r);
int down = T.walkMax(1, n, 0, x);
int up = T.walkMax(1, n, 0, x+1)-1;
int len = r-down+1;
if(up == -2) up = n;
T.updRange(l, down-1, 1);
T.updRange(up-len+1, up, 1);
}else{
cin >> low >> high;
int l = T.walkMax(1, n, 0, low);
int r = T.walkMax(1, n, 0, high+1)-1;
if(r == -2) r = n;
if(l == -1) l = n+1;
ll res = r-l+1;
cout << res << "\n";
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1062 ms |
3876 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
344 KB |
Output is correct |
| 2 |
Correct |
52 ms |
348 KB |
Output is correct |
| 3 |
Correct |
47 ms |
348 KB |
Output is correct |
| 4 |
Correct |
34 ms |
512 KB |
Output is correct |
| 5 |
Execution timed out |
1089 ms |
916 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1051 ms |
808 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1075 ms |
852 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1048 ms |
2136 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1061 ms |
3676 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1040 ms |
3676 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1039 ms |
3676 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1030 ms |
3672 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1089 ms |
3676 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
