#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 1e5;
int n, q;
const int BSIZE = 301;
const int MAXBLOCKS = 333;
int num_blocks;
int numsx[MAXN];
int numsy[MAXN];
pii vecs[MAXN];
int sign(int v) {
if (v == 0) return 0;
if (v < 0) return -1;
return 1;
}
class Block {
public:
vector<int> xstart;
vector<int> xend;
vector<int> ystart;
vector<int> yend;
int shiftx = 0;
int shifty = 0;
int lp, rp;
Block() {}
Block(int lv, int rv) {
lp = lv;
rp = rv;
make();
}
void make() {
xstart.clear();
xend.clear();
ystart.clear();
yend.clear();
for (int i = lp; i <= rp; i++) {
if (i > lp) {
int x1 = numsx[i];
int x2 = numsx[i-1];
int y1 = numsy[i];
int y2 = numsy[i-1];
int mnx = min(x1, x2);
int mxx = max(x1, x2);
int mny = min(y1, y2);
int mxy = max(y1, y2);
xstart.push_back(-mxx);
xend.push_back(-mnx);
ystart.push_back(-mxy);
yend.push_back(-mny);
}
}
sort(xstart.begin(), xstart.end());
sort(ystart.begin(), ystart.end());
sort(xend.begin(), xend.end());
sort(yend.begin(), yend.end());
}
int bs(vector<int> &v, int pos) {
int mn = -1;
int mx = v.size();
while (mx > mn+1) {
int cur = (mn+mx)/2;
if (v[cur] < pos) mn = cur;
else mx = cur;
assert(v[cur] != pos);
}
return mn+1;
}
int get() {
return bs(xstart, shiftx)+bs(ystart, shifty)-bs(xend, shiftx)-bs(yend, shifty);
}
void upd(int l, int r, int vx, int vy) {
for (int i = lp; i <= rp; i++) {
numsx[i] += shiftx;
numsy[i] += shifty;
if (l <= i && i <= r) {
numsx[i] += vx;
numsy[i] += vy;
}
}
shiftx = 0;
shifty = 0;
make();
}
};
Block blocks[MAXBLOCKS];
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> n;
num_blocks = ceil((1.0*(n+1))/BSIZE);
int curx = 1;
int cury = 1;
for (int i = 0; i < n; i++) {
numsx[i] = curx;
numsy[i] = cury;
int x, y; cin >> x >> y;
curx += x;
cury += y;
vecs[i] = pii(x, y);
}
numsx[n] = curx;
numsy[n] = cury;
for (int i = 0; i < num_blocks; i++) {
blocks[i] = Block(BSIZE*i, min(BSIZE*(i+1), n));
}
int pos = 0;
cin >> q;
for (int i = 0; i < q; i++) {
char c; cin >> c;
if (c == 'Q') {
int ans = 0;
for (int j = 0; j < num_blocks; j++) {
ans += blocks[j].get();
if (j < num_blocks-1) {
int x1 = numsx[blocks[j].rp]+blocks[j].shiftx;
int y1 = numsy[blocks[j].rp]+blocks[j].shifty;
int x2 = numsx[blocks[j+1].lp]+blocks[j+1].shiftx;
int y2 = numsy[blocks[j+1].lp]+blocks[j+1].shifty;
ans += (sign(x1) != sign(x2)) + (sign(y1) != sign(y2));
}
}
cout << ans << "\n";
}
if (c == 'B') {
pos = max(pos-1, 0);
}
if (c == 'F') {
pos = min(n-1, pos+1);
}
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);
for (int j = 0; j < num_blocks; j++) {
if (blocks[j].rp <= pos) continue;
if (blocks[j].lp <= pos) {
blocks[j].upd(pos+1, blocks[j].rp, xsh, ysh);
}
else {
blocks[j].shiftx += xsh;
blocks[j].shifty += ysh;
}
}
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
468 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
380 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
468 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
380 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
468 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
380 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
