#include <bits/stdc++.h>
#ifdef LOCAL
#include "/home/trcmai/code/tools.h"
#define debug(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl;
#else
#define debug(x...)
#endif
using namespace std;
#define all(a) a.begin(), a.end()
#define ll long long
#define endl '\n'
const int N = 1e6 + 6, LOG = 27, MOD = 1e9 + 7;
const ll INF = 1e18;
int n,q;
namespace segtree{
int n;
vector<ll>tr,lz;
void init(int sz){
n = sz;
tr.resize(4*n + 5,0);
lz.resize(4*n + 5,0);
}
void push(int i,int l,int r){
if(lz[i] == 0) return;
tr[i] += lz[i];
if(l != r){
lz[2*i] += lz[i];
lz[2*i + 1] += lz[i];
}
lz[i] = 0;
}
void update(int i,int l,int r,int ql,int qr,int val){
push(i,l,r);
if(l > qr || r < ql) return;
if(ql <= l && r <= qr){
lz[i] += val;
push(i,l,r);
return;
}
int m = (r+l) >> 1;
update(2*i,l,m,ql,qr,val);
update(2*i+1,m+1,r,ql,qr,val);
tr[i] = max(tr[2*i],tr[2*i + 1]);
}
ll get(int i,int l,int r,int ql,int qr){
push(i,l,r);
if(l > qr || r < ql) return 0;
if(ql <= l && r <= qr) return tr[i];
int m = (r+l) >> 1;
return max(get(2*i,l,m,ql,qr),get(2*i+1,m+1,r,ql,qr));
}
int walk(int i,int l,int r,ll val){
push(i,l,r);
if(tr[i] < val) return n + 1;
if(l == r) return l;
int m = (r+l) >> 1;
if(tr[2*i] >= val) return walk(2*i,l,m,val);
else return walk(2*i + 1,m + 1,r,val);
}
int walk(ll val){
return walk(1,1,n,val);
}
void update(int l,int r,ll val){
update(1,1,n,l,r,val);
}
ll fval(int pos){
return get(1,1,n,pos,pos);
}
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
auto solver=[&](){
cin>>n>>q;
segtree::init(n);
vector<int>a(n + 1);
for(int i = 1;i <= n;++i) cin>>a[i];
sort(a.begin() + 1,a.end());
for(int i = 1;i <= n;++i){
segtree::update(i,i,a[i]);
}
while(q--){
char t; cin>>t;
if(t == 'F'){
ll tot,val; cin>>tot>>val;
cerr<<"QUERY UPDATE: "<<tot<<" "<<val<<endl;
int l = segtree::walk(val);
if(l > n) continue;
tot = min(tot,(ll)n - l + 1);
ll last_val = segtree::fval(l + tot - 1);
//update first range
int r = segtree::walk(last_val) - 1;
segtree::update(l,r,1);
// update second range
int r2 = segtree::walk(last_val + 1) - 1;
int l2 = r2 - (tot - (r - l + 1)) + 1;
segtree::update(l2,r2,1);
cerr<<"RANGE UPDATE: "<<l<<" "<<l + tot - 1<<endl;
for(int i = 1;i <= n;++i)
cerr<<segtree::fval(i)<<" \n"[i == n];
cerr<<endl;
}else{
ll u,v; cin>>u>>v;
cerr<<"QUERY ANS: "<<u<<" "<<v<<endl;
int l = segtree::walk(u);
int r = segtree::walk(v + 1);
cerr<<"RANGE ANS: "<<l<<" "<<r<<endl;
cout<< r - l << endl;
}
}
};
int t = 1; // cin>>t;
while (t--) solver();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1088 ms |
8592 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
81 ms |
628 KB |
Output is correct |
| 2 |
Correct |
273 ms |
848 KB |
Output is correct |
| 3 |
Correct |
150 ms |
848 KB |
Output is correct |
| 4 |
Correct |
97 ms |
608 KB |
Output is correct |
| 5 |
Execution timed out |
1042 ms |
3052 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1048 ms |
2444 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1055 ms |
2332 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1055 ms |
6888 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1053 ms |
7480 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1056 ms |
7000 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1045 ms |
9408 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1026 ms |
8260 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1051 ms |
10068 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
