#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif
// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
//#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define FF first
#define SS second
#define all(a) a.begin(), a.end()
#define mod (ll)(1000000007)
const int pr=18, s_p=1<<(pr), e_p=(1<<(pr+1))-1;
int n, m;
vector<int>A, S_sum;
void pre(){
A.clear(), S_sum.clear();
A.resize(n), S_sum.resize(1<<(pr+1));
}
void update(int ind, int c){
S_sum[ind]+=c;
while(ind/=2)
S_sum[ind]+=c;
}
int get(int id, int u, int v, int l, int r){
if(l>v || r<u)
return 0;
if(l>=u && r<=v)
return S_sum[id];
int md=(l+r)/2;
return get(id*2, u, v, l, md)+get(id*2+1, u, v, md+1, r);
}
int get_pos(int id, int bef, int sum, bool fir, int l, int r){
if((fir && bef+S_sum[id]<sum) || (!fir && bef>sum) || l>n-1+s_p)
return -1;
if(l==r){
if(fir){
if(bef+S_sum[id]>=sum)
return l-s_p;
}
else{
if(bef+S_sum[id]<=sum)
return l-s_p;
}
return -1;
}
int md=(l+r)/2;
if(fir){
int res=get_pos(id*2, bef, sum, fir, l, md);
if(res!=-1)
return res;
return get_pos(id*2+1, bef+S_sum[id*2], sum, fir, md+1, r);
}
else{
int res=get_pos(id*2+1, bef+S_sum[id*2], sum, fir, md+1, r);
if(res!=-1)
return res;
return get_pos(id*2, bef, sum, fir, l, md);
}
}
int calc(int u, int v){
if(u>v)
return 0;
return get(1, u+s_p, v+s_p, s_p, e_p);
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>m;
cout<<endl;
pre();
for(int i=0;i<n;i++){
cin>>A[i];
}
sort(all(A));
for(int i=n-1;i>0;i--){
A[i]-=A[i-1];
update(i+s_p, A[i]);
}
update(s_p, A[0]);
while(m--){
char type;
int x, y;
cin>>type>>x>>y;
if(type=='F'){
// change
int l=get_pos(1, 0, y, 1, s_p, e_p);
if(l==-1)
continue;
int r=min(n-1, l+x-1);
int diff=r-l+1;
if(calc(0, l)==calc(0, r)){
while(r+1<n && A[r+1]==0)
r++;
l=max(0, r-x+1);
assert(diff==r-l+1);
//assert(calc(0, get_pos(1, 0, y, 1, s_p, e_p))==calc(0, l));
A[l]++, update(l+s_p, 1);
if(r+1<n)
A[r+1]--, update(r+1+s_p, -1);
continue;
}
int need=calc(0, r);
int r_fir=get_pos(1, 0, need, 1, s_p, e_p);
int r_las=get_pos(1, 0, need, 0, s_p, e_p);
A[l]++, update(l+s_p, 1);
if(r_las+1<n)
A[r_las+1]--, update(r_las+1+s_p, -1);
if(r!=r_las){
A[r_fir]--, update(r_fir+s_p, -1),
A[r_las-(r-r_fir)]++, update(r_las-(r-r_fir)+s_p, 1);
}
}
else{
// print
int l=get_pos(1, 0, x, 1, s_p, e_p);
int r=get_pos(1, 0, y, 0, s_p, e_p);
int ans=r-l+1;
if(l==-1 || r==-1 || l>r)
ans=0;
cout<<ans<<endl;
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
15 ms |
5464 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2392 KB |
Output is correct |
| 3 |
Correct |
3 ms |
2392 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2392 KB |
Output is correct |
| 5 |
Runtime error |
24 ms |
4688 KB |
Execution killed with signal 6 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
4696 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
4696 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
5208 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
5208 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
5208 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
94 ms |
3152 KB |
Output is correct |
| 2 |
Runtime error |
14 ms |
5208 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
17 ms |
5468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
73 ms |
3408 KB |
Output is correct |
