// #include <bits/stdc++.h>
// using namespace std;
// const int maxnm = 100000;
// const int segnm = (1<<18);
// int n, m;
// int trees[maxnm];
// int ts[maxnm];
// int seg[segnm];
// int flag[segnm];
// void upd1(int p, int l, int r, int k) {
// if (k < l || r < k) return;
// if (l == r) {
// seg[p]++;
// return;
// }
// int mid = (l + r) >> 1;
// upd1(2*p, l, mid, k); upd1(2*p+1, mid+1, r, k);
// seg[p] = seg[2*p] + seg[2*p + 1];
// }
// void push(int p, int l, int r) {
// if (l == r) {
// flag[p] = 0;
// return;
// }
// int mid = (l + r) >> 1;
// seg[2*p] *= (flag[p] ^ 1); seg[2*p + 1] *= (flag[p] ^ 1);
// flag[2*p] = flag[2*p + 1] = flag[p];
// flag[p] = 0;
// }
// int upd2(int p, int l, int r, int mh, int R) {
// push(p, l, r);
// if (l <= mh) {
// if (seg[p] <= R) {
// seg[p] = 0; flag[p] = 1;
// return R - seg[p];
// }
// int mid = (l + r) >> 1;
// int x = upd2(2*p, l, mid, mh, R);
// if (x > 0) upd2(2*p + 1, mid+1, r, mh, R - x);
// return 0;
// }
// int mid = (l + r) >> 1;
// int x = upd2(2*p, l, mid, mh, R);
// if (x > 0) x = upd2(2*p+1, mid+1, r, mh, R - x);
// return x;
// }
// int qry(int p, int l, int r, int L, int R) {
// push(p, l, r);
// if (R < l || r < L) return 0;
// if (L <= l && r <= R) return seg[p];
// int mid = (l + r) >> 1;
// return qry(2*p, l, mid, L, R) + qry(2*p + 1, mid+1, r, L, R);
// }
// void print(int p, int l, int r) {
// push(p, l, r);
// if (l == r) {
// cout << seg[p] << " "; return;
// } int mid = (l+r)>>1;
// print(2*p, l, mid); print(2*p + 1, mid+1, r);
// }
// int main() {
// cin >> n >> m;
// for (int i = 0; i < n; i++) {
// cin >> trees[i];
// ts[i] = i;
// }
// sort(ts, ts+n, [](int a, int b){ return trees[a] < trees[b]; });
// int counter = 0; map<int, int> M;
// for (int i = 0; i < n; i++) {
// upd1(1, 0, n-1, counter);
// M[trees[ts[i]]] = counter;
// if (trees[ts[i]] < trees[ts[i + 1]]) counter++;
// }
// for (int i = 0; i < m; i++) {
// char t; int a, b; cin >> t >> a >> b;
// if (t == 'F') {
// upd2(1, 0, n-1, b, a);
// cout << "------------------" << endl;
// print(1, 0, n-1); cout << endl;
// cout << "------------------" << endl;
// } else {
// a = M[a], b = M[b];
// cout << a << " " << b << " ";
// cout << qry(1, 0, n-1, a, b) << '\n';
// }
// }
// return 0;
// }
#include <bits/stdc++.h>
using namespace std;
const int maxnm = 100000;
const int segnm = (1<<18);
int n, m;
int trees[maxnm];
pair<int,int> seg[segnm];
int flg[segnm];
void form(int p, int l, int r) {
seg[p] = {max(seg[2*p].first, seg[2*p+1].first), min(seg[2*p].second, seg[2*p+1].second)};
}
void build(int p, int l, int r) {
if (l == r) {
// cout << p << " " << l << " " << r << " " << trees[l] << endl;
seg[p] = {trees[l], trees[l]};
// cout << seg[p].first << " " << seg[p].second << endl;
return;
}
int mid = (l + r)/2;
build(2*p, l, mid); build(2*p + 1, mid+1, r);
form(p, l, r);
// cout << seg[p].first << " " << seg[p].second << endl;
}
void push(int p, int l, int r) {
if (l == r) { flg[p] = 0; return; }
seg[2*p].first += flg[p]; seg[2*p+1].first += flg[p];
seg[2*p].second += flg[p]; seg[2*p+1].second += flg[p];
flg[2*p] += flg[p]; flg[2*p+1] += flg[p];
flg[p] = 0;
}
void upd(int p, int l, int r, int L, int R) {
push(p, l, r);
if (r < L || R < l) return;
if (L <= l && r <= R) {
// cout << "UPD " << l << " " << r << " " << L << " " << R << endl;
seg[p].first++; seg[p].second++;
flg[p]++;
return;
}
int mid = (l + r)/2;
upd(2*p, l, mid, L, R);
upd(2*p + 1, mid+1, r, L, R);
form(p, l, r);
}
int qryMin(int p, int l, int r, int k) {
push(p, l, r);
if (l == r) return l;
int mid = (l + r) / 2;
if (seg[2*p].first < k) return qryMin(2*p+1, mid+1, r, k);
else return qryMin(2*p, l, mid, k);
}
int qryMax(int p, int l, int r, int k) {
push(p, l, r);
if (l == r) return l;
int mid = (l + r) / 2;
if (seg[2*p+1].second > k) return qryMax(2*p, l, mid, k);
else return qryMax(2*p + 1, mid+1, r, k);
}
void print(int p, int l, int r) {
push(p, l, r);
if (l == r) cout << p << " " << l << " " << r << " " << seg[p].first << " " << seg[p].second << endl;
if (l == r) return;
print(2*p, l, (l+r)/2);
print(2*p+1, (l+r)/2+1, r);
}
int qry(int p, int l, int r, int k) {
push(p, l, r);
if (k < l || r < k) {
return -2000000000;
}
if (l == r) {
return seg[p].first;
}
int mid = (l + r)/2;
return max(qry(2*p, l, mid, k), qry(2*p + 1, mid+1, r, k));
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> trees[i];
sort(trees, trees + n);
build(1, 0, n-1);
// cout << endl;
// print(1, 0, n-1);
// cout << endl;
// for (int j = 0; j < n; j++) cout << qry(1, 0, n-1, j) << " ";
// cout << endl;
// cout << endl;
for (int i = 0; i < m; i++) {
char t; cin >> t; int a, b; cin >> a >> b;
if (t == 'F') {
int minstart = qryMin(1, 0, n-1, b);
// cout << minstart << endl;
if (minstart + a - 1 >= n) {
// upd(1, 0, n-1, minstart, n-1);
continue;
}
// cout << minstart + a - 1 << " " << 0 << " " << n-1 << endl;
int k = qry(1, 0, n-1, minstart + a - 1);
int maxstart = qryMin(1, 0, n-1, k);
int maxend = qryMax(1, 0, n-1, k);
if (minstart == maxstart) {
// cout << minstart << " " << minstart + a - 1 << endl;
upd(1, 0, n-1, minstart, minstart + a - 1);
continue;
}
// cout << minstart << " " << maxstart << " " << maxend << endl;
// cout << minstart << " " << maxstart -1 << " " << maxend - (maxstart - minstart) + 1 << " " << maxend << endl;
upd(1, 0, n-1, minstart, maxstart - 1);
upd(1, 0, n-1, maxend - (maxstart - minstart) + 1, maxend);
} else {
int c = qryMin(1, 0, n-1, a);
int d = qryMax(1, 0, n-1, b);
if (qry(1, 0, n-1, c) > b || qry(1, 0, n-1, d) < a) {
cout << 0 << '\n';
continue;
}
cout << d-c+1 << '\n';
}
// print(1, 0, n-1); cout << endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
187 ms |
4940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
190 ms |
1552 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
215 ms |
1744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
170 ms |
3136 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
160 ms |
4736 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
188 ms |
4940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
234 ms |
5452 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
200 ms |
5092 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
288 ms |
5968 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
