#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef pair<int, int> pii;
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> ostree;
const int MAXN = 1e5;
int n, q;
int l_cross = 0;
int xelems[MAXN+1];
int yelems[MAXN+1];
pii vecs[MAXN];
int pos = 0;
void er(ostree &s, pii v) {
s.erase(s.find(v));
}
void print(ostree &s) {
for (pii p: s) cout << p.first << " ";
cout << endl;
}
class right_ds {
public:
int lz = 0;
ostree mn_elems;
ostree mx_elems;
right_ds() {}
right_ds(int elems[]) {
for (int i = 0; i < n; i++) {
mn_elems.insert(pii(min(elems[i], elems[i+1]), i));
mx_elems.insert(pii(max(elems[i], elems[i+1]), i));
}
}
int query() {
pii qelem(-lz+1, -1);
return mn_elems.order_of_key(qelem)-mx_elems.order_of_key(qelem);
}
void del(int elems[], int pos) { // del, then ++
int mne = min(elems[pos], elems[pos+1]);
int mxe = max(elems[pos], elems[pos+1]);
er(mn_elems, pii(mne, pos));
er(mx_elems, pii(mxe, pos));
elems[pos] += lz;
if (mne <= -lz && mxe > -lz) l_cross++;
}
void ins(int elems[], int pos) { // --, then ins
elems[pos] -= lz;
int mne = min(elems[pos], elems[pos+1]);
int mxe = max(elems[pos], elems[pos+1]);
mn_elems.insert(pii(mne, pos));
mx_elems.insert(pii(mxe, pos));
if (mne <= -lz && mxe > -lz) l_cross--;
}
};
right_ds xds;
right_ds yds;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> n;
xelems[0] = 1;
yelems[0] = 1;
for (int i = 1; i <= n; i++) {
int x, y; cin >> x >> y;
xelems[i] = xelems[i-1]+x;
yelems[i] = yelems[i-1]+y;
vecs[i] = pii(x, y);
}
xds = right_ds(xelems);
yds = right_ds(yelems);
cin >> q;
xds.del(xelems, pos);
yds.del(yelems, pos);
pos++;
for (int i = 0; i < q; i++) {
char c; cin >> c;
// print(xds.mn_elems);
// print(xds.mx_elems);
if (c == 'F') {
if (pos == n) continue;
xds.del(xelems, pos);
yds.del(yelems, pos);
pos++;
}
if (c == 'B') {
if (pos == 1) continue;
pos--;
xds.ins(xelems, pos);
yds.ins(yelems, pos);
}
if (c == 'Q') {
cout << (l_cross+xds.query()+yds.query()) << "\n";
}
if (c == 'C') {
int x, y; cin >> x >> y;
int xsh = x-vecs[pos].first;
int ysh = y-vecs[pos].second;
vecs[pos] = pii(x, y);
xds.lz += xsh;
yds.lz += ysh;
}
}
};
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
