#include <bits/stdc++.h>
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define per(i,a,b) for (auto i = (b); i >= (a); --i)
#define all(x) begin(x),end(x)
#define siz(x) int((x).size())
#define Mup(x,y) x=max(x,y)
#define mup(x,y) x=min(x,y)
#define fi first
#define se second
#define dbg(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
using ii = pair<int,int>;
using ll = long long;
const int INF = 1e9;
template <const int N = 1<<17>
struct lazy {
struct node { ll sum; int right; };
node merge(node x, node y){ return {x.sum+y.sum,y.right}; }
node v[2*N]{}; int z[2*N]{};
lazy(int *f, int *l) {
rep(i,f,l-1) v[N+i-f] = {*i,*i};
rep(i,l-f,N-1) v[N+i] = {INF,INF};
per(i,1,N-1) v[i] = merge(v[2*i],v[2*i+1]);
}
void prop(int k, int s, int e) {
v[k].sum += z[k]*ll(e-s+1);
v[k].right += z[k];
if (s != e) {
z[2*k] += z[k];
z[2*k+1] += z[k];
}
z[k] = 0;
}
void update(int a, int b, int k = 1, int s = 0, int e = N-1) {
prop(k,s,e);
if (a <= s and e <= b) { z[k]++, prop(k,s,e); return; }
if (b < s or e < a) return;
int m = (s+e)/2;
update(a,b,2*k,s,m), update(a,b,2*k+1,m+1,e);
v[k] = merge(v[2*k],v[2*k+1]);
}
ll query(int a, int b, int k = 1, int s = 0, int e = N-1) {
prop(k,s,e);
if (a <= s and e <= b) return v[k].sum;
if (b < s or e < a) return v[0].sum;
int m = (s+e)/2;
return query(a,b,2*k,s,m) + query(a,b,2*k+1,m+1,e);
}
int lb(int x, int k = 1, int s = 0, int e = N-1) {
int m;
prop(k,s,e);
while (s < e) {
m = (s+e)/2;
prop(2*k,s,m), prop(2*k+1,m+1,e);
if (x <= v[2*k].right) k = 2*k, e = m;
else k = 2*k+1, s = m+1;
}
if (x <= v[k].right) return s;
else return s+1;
}
};
const int N = 1e5+3, M = N;
int n, m, a[N];
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
rep(i,1,n) cin >> a[i];
sort(a+1,a+n+1);
lazy seg(a,a+n+1);
rep(i,1,m) {
char c; int x, y; cin >> c >> x >> y;
if (c == 'F') {
// 높이가 y 이상인 가장 작은 나무 x개
int f1 = seg.lb(y);
if (f1 > n) continue;
int s = y, e = INF, m;
while (s <= e) {
m = (s+e)/2;
if (min(n+1,seg.lb(m+1))-f1 <= x) s = m+1;
else e = m-1;
}
// [y,e]에 속한 나무의 개수가 x 이하인 최대의 e
int l1 = min(n,seg.lb(e+1)-1); // [y,e]의 나무들에 1씩 더함
int l2, f2;
if (f1 <= l1) {
seg.update(f1,l1);
l2 = min(n,seg.lb(s+1)-1); // s의 나무들 중 뒷쪽부터 1씩 더할 예정
f2 = max(l1+1,l2-(x-(l1-f1+1))+1);
} else {
l2 = min(n,seg.lb(s+1)-1); // s의 나무들 중 뒷쪽부터 1씩 더할 예정
f2 = max(f1,l2-x+1);
}
if (f2 <= l2) seg.update(f2,l2);
} else cout << min(n+1,seg.lb(y+1))-min(n+1,seg.lb(x)) << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
105 ms |
7012 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5460 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
5460 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
73 ms |
6576 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
60 ms |
6696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
201 ms |
6732 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
247 ms |
6920 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
229 ms |
6792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
317 ms |
7424 KB |
Output is correct |
| 2 |
Incorrect |
250 ms |
7032 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
213 ms |
7172 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
95 ms |
8116 KB |
Output is correct |
