| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 27399 | youngyojun | Ruka (COI15_ruka) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <string>
#include <tuple>
#define rf(x) (x)=0;while(*p<48)im=*p=='-';while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);if(im)(x)=-(x);
#define pb push_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
#define MAXX (255000000)
#define MAXN (100005)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
struct SEG {
SEG() : l(NULL), r(NULL), d(0) {}
SEG *l, *r;
int d;
void upd(int x, int R, int s = -MAXX, int e = MAXX) {
if(x < s || e < x) return;
d += R; if(s == e) return;
int m = (s+e)/2;
if(x <= m) {
if(NULL == l) l = new SEG();
l -> upd(s, m, x, R);
} else {
if(NULL == r) r = new SEG();
r -> upd(m+1, e, x, R);
}
}
int get(int p, int q, int s = -MAXX, int e = MAXX) {
if(q < p || q < s || e < p) return 0;
if(p <= s && e <= q) return d;
int m = (s+e)/2;
return (l ? l -> get(p, q, s, m) : 0) + (r ? r -> get(p, q, m+1, e) : 0);
}
};
struct Node {
Node() : pt(1), px(0) {
upseg = new SEG();
downseg = new SEG();
}
SEG *upseg, *downseg;
pii L[MAXN];
int N, pt, px;
void updseg(SEG& seg, pii l, int a, int b) {
if(l.first > l.second) swap(l.first, l.second);
seg.upd(l.first, a); seg.upd(l.second+1, b);
}
void init(int _N, int X[]) {
N = _N; L[1] = {1, X[1]};
for(int i = 2; i <= N; i++) L[i] = {X[i-1], X[i]};
for(int i = 1; i <= N; i++) updseg(downseg, L[i], 1, -1);
}
void upf() {
if(1 == pt) return; pt--;
updseg(upseg, L[pt], -1, 1);
L[pt].first += px;
L[pt].second += px;
updseg(downseg, L[pt], 1, -1);
}
void downf() {
if(N == pt) return;
updseg(downseg, L[pt], -1, 1);
L[pt].first -= px;
L[pt].second -= px;
updseg(upseg, L[pt], 1, -1);
pt++;
}
void mvf(int dx) {
int dl = L[pt].first - L[pt].second + dx;
L[pt].second = L[pt].first + dx;
L[pt].first -= dl; L[pt].second -= dl;
px += dl;
}
int getAns() { return upseg.get(-MAXX, 0) + downseg.get(-MAXX, px); }
};
Node nX, nY;
int X[MAXN], Y[MAXN];
int N, M;
void f(int d[]) { d[0] = 1; for(int i = 1; i <= N; i++) d[i] += d[i-1]; }
int main() {
scanf("%d", &N);
for(int i = 1; i <= N; i++) scanf("%d%d", &X[i], &Y[i]);
f(X); f(Y); nX.init(N, X); nY.init(N, Y);
for(scanf("%d", &M); M--;) {
char c; scanf(" %c", &c);
if('Q' == c) printf("%d\n", nX.getAns() + nY.getAns());
else if('B' == c) { nX.upf(); nY.upf(); }
else if('F' == c) { nX.downf(); nY.downf(); }
else {
int dx, dy; scanf("%d%d", &dx, &dy);
nX.mvf(dx); nY.mvf(dy);
}
}
return 0;
}