| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 27316 |
2017-07-12T08:07:46 Z |
윤교준(#1144) |
Ruka (COI15_ruka) |
C++11 |
|
3 ms |
62284 KB |
#include <bits/stdc++.h>
#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 befv(V) ((V)[(sz(V)-2)])
#define allv(V) ((V).begin()),((V).end())
#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 rb(x) ((x)&(-(x)))
#define upmax(a,b) (a)=max((a),(b))
#define upmin(a,b) (a)=min((a),(b))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
#define MOD (1000000007)
#define MAXN (100005)
#define SQN (335)
#define DSN (MAXN/SQN + 5)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
static unsigned char str[55555555], *p = str;
static bool im = false;
const int MX = 131072;
struct BIT {
int d[MX], t[MX];
void _upd(int x, int r) { for(; x < MX; x += rb(x)) d[x] += r; }
void upd(int x, int r) { _upd(x, -t[x] + r); t[x] = r; }
int get(int x) {
int r = 0; for(; x; x -= rb(x)) r += d[x];
return r;
}
int get(int s, int e) { return get(e) - get(s-1); }
};
struct SEG {
int d[MX*2];
void upd(int x, int r) { for(x += MX, d[x] = r, x /= 2; x; x /= 2) d[x] = d[x*2] + d[x*2+1]; }
int get(int s, int e) {
int r = 0; for(s += MX, e += MX; s <= e; s /= 2, e /= 2) {
if(s&1) r += d[s++]; if(~e&1) r += d[e--];
} return r;
}
int get(int x) { return get(x, x); }
};
struct Node {
int VX[DSN*2], S[DSN*2];
int N, cx, cp;
void init() {}
void mv(int dx) { cx += dx; cp = 0; }
void make(vector<pii>& V) {
N = cx = cp = 0; if(V.empty()) return;
vector<pii> Q;
for(pii& v : V) {
if(v.first > v.second) swap(v.first, v.second);
v.second++;
Q.pb({v.first, 1}); Q.pb({v.second, -1});
}
sorv(Q);
VX[0] = S[0] = 0;
for(int i = 0, j; i < sz(Q); i = j) {
for(j = i+1; j < sz(Q) && Q[i].first == Q[j].first; j++);
N++; S[N] = S[N-1]; VX[N] = Q[i].first;
for(int k = i; k < j; k++) S[N] += Q[k].second;
}
}
int get(int X = 0) {
if(!N) return 0;
if(!cp) {
X -= cx;
if(X < VX[1] || VX[N] < X) {
cp = -1;
return 0;
}
int idx = (int)(lower_bound(VX+1, VX+N+1, X) - VX);
if(VX[idx] != X) idx--;
cp = idx;
}
return cp < 0 ? -1 : S[cp];
}
void debug() {
printf("N = %d, cx = %d\n", N, cx);
for(int i = 1; i <= N; i++) printf("VX[%d] = %d, S[%d] = %d\n", i, VX[i], i, S[i]);
puts("\n");
}
};
BIT bitX, bitY;
Node nodeX[SQN], nodeY[SQN];
int X[MAXN], Y[MAXN];
int N, M, pt = 1;
void initNode(int i) {
int s = i*SQN + 1, e = min(N, (i+1)*SQN);
vector<pii> V;
for(int l = s; l <= e; l++) V.pb({bitX.get(l), bitX.get(l+1)});
nodeX[i].make(V); clv(V);
for(int l = s; l <= e; l++) V.pb({bitY.get(l), bitY.get(l+1)});
nodeY[i].make(V);
}
void initNode() {
for(int i = 0; i < SQN; i++) {
if(N <= i*SQN) break;
initNode(i);
}
}
void f(int dx, int dy) {
for(int i = 0; i < SQN; i++) {
int s = i*SQN + 1, e = (i+1)*SQN;
if(N < s) break;
if(e < pt) continue;
if(s <= pt && pt <= e) initNode(i);
else { nodeX[i].mv(dx); nodeY[i].mv(dy); }
}
}
int getAns() {
int ret = 0;
for(int i = 0; i < SQN; i++) {
if(N <= i*SQN) break;
ret += nodeX[i].get() + nodeY[i].get();
}
return ret;
}
int main() {
//time_t __s = clock(), __e;
fread(str, 1, 55555555, stdin);
rf(N)
X[1] = Y[1] = 1; for(int i = 1; i <= N; i++) {
int dx, dy; rf(dx) rf(dy)
X[i+1] = X[i] + dx; Y[i+1] = Y[i] + dy;
}
for(int i = 1; i <= N+1; i++) {
bitX.upd(i, X[i] - X[i-1]);
bitY.upd(i, Y[i] - Y[i-1]);
}
//__e = clock();
//fprintf(stderr, "INPUT TIME : %lfs\n", (double)(__e - __s) / CLOCKS_PER_SEC);
//__s = clock();
initNode();
//__e = clock();
//fprintf(stderr, "INIT TIME : %lfs\n", (double)(__e - __s) / CLOCKS_PER_SEC);
rf(M) while(M--) {
//__s = clock();
while(*p<48)p++; char c = *p++;
if('F' == c) pt = min(pt+1, N);
else if('B' == c) pt = max(1, pt-1);
else if('Q' == c) printf("%d\n", getAns());
else {
int dx, dy; rf(dx) rf(dy)
//int rx = dx - bitX.t[pt+1], ry = dy - bitY.t[pt+1];
int rx = dx - bitX.get(pt, pt+1), ry = dy - bitY.get(pt, pt+1);
bitX.upd(pt+1, dx); bitY.upd(pt+1, dy);
f(rx, ry);
}
//__e = clock();
//fprintf(stderr, "CAL %d TIME : %lfs\n", M, (double)(__e - __s) / CLOCKS_PER_SEC);
}
return 0;
}
Compilation message
ruka.cpp: In function 'int main()':
ruka.cpp:126:32: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
fread(str, 1, 55555555, stdin);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
62284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
62284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
62284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
