//MOI Prep Set 1
#include<bits/stdc++.h>
using namespace std;
#define ll 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);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
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;
}
}
if (lb == n)continue;
int rb = lb + ci - 1;
rb = min(rb, n-1);
//debug(lb);
//debug(rb);
if (rb < n - 1 && val(rb) + a[rb] == val(rb+1) + a[rb + 1]){
//edge case
int kb = lower_bound(a.begin(), a.end(), a[rb]) - a.begin();
kb--;
//debug(kb);
if(lb<=kb)upd(lb,kb);
// cout<<a[0]+val(0);
int rem = rb - lb + 1 - max(0, kb - lb + 1);
kb = upper_bound(a.begin(), a.end(), a[rb]) - a.begin();
--kb;
// debug(kb);
// debug(kb - rem + 1);
upd(kb - rem + 1,kb);
}else{
upd(lb,rb);
}
}else{
int l = 0, r = n - 1;
int lb = 0;
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 (a[lb] + val(lb)>= ci && a[rb] + val(rb)<= h){
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;
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
165 ms |
4332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
126 ms |
1548 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
113 ms |
2004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
155 ms |
2920 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
169 ms |
4020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
121 ms |
4160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
273 ms |
4808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
221 ms |
4540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
330 ms |
5348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
