#include "bits/stdc++.h"
using namespace std;
#define forR(i, a) for(int i=0; (i) < (a); ++(i))
#define REP(i, a, b) for(int i=(a); (i) < (b); ++(i))
#define open(x) freopen(((string) x + ".in").c_str(), "r", stdin); freopen(((string) x + ".out").c_str(), "w", stdout);
#define boost() cin.sync_with_stdio(0); cin.tie(0)
#define all(a) (a).begin(), (a).end()
typedef long long ll;
const int MN = 1e5 + 10, ME = 4 * MN, INF=1e8;
struct node{
int l, r, lz;
};
node seg[ME];
int a[MN];
void push(int v){
if(2*v+1 < ME){
seg[2*v].l += seg[v].lz;
seg[2*v+1].l += seg[v].lz;
seg[2*v].r += seg[v].lz;
seg[2*v+1].r += seg[v].lz;
seg[2*v].lz += seg[v].lz;
seg[2*v+1].lz += seg[v].lz;
seg[v].lz = 0;
}
}
void up(int v){
seg[v].l = seg[2*v].l;
seg[v].r = seg[2*v+1].r;
}
void build(int v, int nl, int nr){
if(nl > nr) return;
else if(nl == nr) seg[v] = {a[nl], a[nr], 0};
else {
int mid = (nl + nr) / 2;
build(2*v, nl, mid);
build(2*v+1, mid+1, nr);
up(v);
}
}
int las(int v, int nl, int nr, int val){
push(v);
if(seg[v].l >= val){
throw;
}
if(nl == nr) return nl;
else {
int mid = (nl + nr) / 2;
if(seg[2*v+1].l < val) return las(2*v+1, mid+1, nr, val);
else return las(2*v, nl, mid, val);
}
}
void upd(int v, int nl, int nr, int l, int r){
push(v);
if(l > r) return;
else if(nl == l && nr == r){
seg[v].l += 1;
seg[v].r += 1;
seg[v].lz += 1;
} else {
int mid = (nl + nr) / 2;
upd(2*v, nl, mid, l, min(r, mid));
upd(2*v+1, mid+1, nr, max(mid+1, l), r);
up(v);
}
}
int val(int v, int nl, int nr, int i){
push(v);
if(nl == i && nr == i) return seg[v].l;
else {
int mid = (nl + nr) / 2;
if(i <= mid) return val(2*v, nl, mid, i);
else return val(2*v+1, mid+1, nr, i);
}
}
signed main(){
boost();
int n, m; cin >> n >> m;
REP(i, 1, n + 1) cin >> a[i];
sort(a+1, a+n+1);
a[0] = -INF;
build(1,0,n);
forR(g, m){
char ins; int p, q;
cin >> ins >> p >> q;
if(ins == 'F'){
int st=las(1,0,n,q)+1;
int fi=min(n, st+p-1);
int fv=val(1,0,n,fi);
int j=las(1,0,n,fv);
// take st...j
int ex = fi-j;
int en=las(1,0,n,fv+1);
// take en-ex+1...en
upd(1,0,n,st,j);
upd(1,0,n,en-ex+1,en);
} else {
int lef=las(1, 0, n, p)+1, rig=las(1,0,n, q+1);
cout << rig - lef + 1 << '\n';
}
// REP(i, 1, n + 1) cout << val(1,0,n,i) << ' ';
// cout << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
6600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
2 ms |
468 KB |
Output is correct |
| 3 |
Correct |
2 ms |
468 KB |
Output is correct |
| 4 |
Correct |
1 ms |
468 KB |
Output is correct |
| 5 |
Correct |
35 ms |
1756 KB |
Output is correct |
| 6 |
Incorrect |
40 ms |
2016 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
1824 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
1976 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
56 ms |
4708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
84 ms |
6376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
6520 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
107 ms |
7088 KB |
Output is correct |
| 2 |
Incorrect |
90 ms |
6628 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
86 ms |
6716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
70 ms |
7724 KB |
Output is correct |
