//MOI Prep Set 1
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define debug(x) cout << "["<<(#x) << " -> " << (x) << "]\n";
int n, m;
vector<ll>a;
int Seg[100001 * 4];
int lz[100001 * 4];
void propagate(int k ,int l, int r){
if (lz[k] != 0){
Seg[k] += (r - l + 1) * lz[k];
if (l != r){
lz[k * 2] += lz[k];
lz[k * 2+ 1]+=lz[k];
}
lz[k] = 0;
}
}
void upd(int l1, int r1, int l = 0, int r = n - 1, int k = 1){
propagate(k,l,r);
// if (l1 > r1)return;
if (l >= l1 && r <= r1){
lz[k]++;
propagate(k,l,r);
return;
}
if (l > r1 || r < l1)return;
upd(l1,r1,l,(l+r)/2,k*2);
upd(l1,r1,(l+r)/2+1,r,k*2+1);
Seg[k] = Seg[k * 2 + 1] + Seg[k * 2];
}
int val(int l1, int l = 0, int r = n - 1, int k = 1){
propagate(k,l,r);
if (l == r){
return Seg[k];
}
int mid =(l+r)/2;
if(l1 <= mid) return val(l1,l,(l+r)/2,k*2);
else return val(l1,(l+r)/2+1,r,k*2+1);
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
cin >> n >> m;
a.resize(n);
for (int i = 0; i < n; ++i){
cin >> a[i];
}
sort(a.begin(), a.end());
while(m--){
char c;
int ci,h;
cin >> c >> ci >> h;
if (c == 'F'){
int l = 0, r = n - 1, lb = n;
while(l<=r){
int mid = (l + r) / 2;
if (a[mid] + val(mid) >= h){
r = mid - 1;
lb = mid;
}else{
l = mid + 1;
}
}
int rb = lb + ci - 1;
if (rb >= n-1){
upd(lb,n-1);
continue;
}
if (a[rb] + val(rb) == a[rb + 1] + val(rb + 1)){
int kb = -1;
l = 0, r = n - 1;
while(l<=r){
int mid = (l + r) / 2;
if (a[mid] + val(mid) >= a[rb] + val(rb)){
r = mid - 1;
kb = mid;
}else{
l = mid + 1;
}
}
--kb;
if (lb<=kb)upd(lb,kb);
int taken = 0;
//debug(lb);debug(kb);debug(rb);
if (lb<=kb)taken = kb - lb + 1;
l = 0, r = n - 1;
kb = n;
while(l<=r){
int mid = (l + r) / 2;
if (a[mid] + val(mid) > a[rb] + val(rb)){
r = mid - 1;
kb = mid;
}else{
l = mid + 1;
}
}
--kb;
upd(kb - ((rb - lb + 1) - taken) + 1, kb);
}else{
upd(lb,rb);
}
}else{
int l = 0, r = n - 1;
int lb = n;
int rb = n - 1;
while(l<=r){
int mid = (l + r)/2;
if (val(mid)+ a[mid] >=ci){
r = mid - 1;
lb = mid;
}else{
l = mid + 1;
}
}
l = 0, r = n -1;
while(l<=r){
int mid = (l + r) / 2;
if (val(mid)+ a[mid] > h){
r = mid - 1;
}else{
l = mid + 1;
rb = mid;
}
}
// cout<<endl;
if (lb != n){
cout<<rb - lb + 1<<'\n';
}else{
cout<<0<<'\n';
}
}
// cout<<endl;
//for (int i =0 ; i < n; i++)cout<<a[i] + val(i)<<" ";
//cout<<endl;
}
// for (int i =0 ; i < n; i++)cout<<a[i] + val(i)<<" ";
// cout<<endl;
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
281 ms |
5392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
166 ms |
972 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
145 ms |
1060 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
281 ms |
3092 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
350 ms |
5068 KB |
Output is correct |
| 2 |
Incorrect |
387 ms |
6424 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
285 ms |
5200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
307 ms |
5256 KB |
Output is correct |
| 2 |
Incorrect |
413 ms |
6484 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
359 ms |
5300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
289 ms |
5712 KB |
Output is correct |
