| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 27307 |
2017-07-12T07:39:39 Z |
윤교준(#1144) |
Ruka (COI15_ruka) |
C++11 |
|
2000 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 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;
void init() {}
void mv(int dx) { cx += dx; }
void make(vector<pii>& V) {
N = cx = 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;
X -= cx;
if(X < VX[1] || VX[N] < X) return 0;
int idx = (int)(lower_bound(VX+1, VX+N+1, X) - VX);
if(VX[idx] != X) idx--;
return S[idx];
}
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");
}
};
SEG segX, segY;
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({segX.get(1, l), segX.get(1, l+1)});
nodeX[i].make(V); clv(V);
for(int l = s; l <= e; l++) V.pb({segY.get(1, l), segY.get(1, 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 = min(N, (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++) {
segX.upd(i, X[i] - X[i-1]);
segY.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 - segX.get(pt+1), ry = dy - segY.get(pt+1);
segX.upd(pt+1, dx); segY.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:110: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 |
Correct |
6 ms |
62284 KB |
Output is correct |
| 2 |
Correct |
0 ms |
62284 KB |
Output is correct |
| 3 |
Correct |
116 ms |
62284 KB |
Output is correct |
| 4 |
Correct |
83 ms |
62284 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
62284 KB |
Output is correct |
| 2 |
Correct |
0 ms |
62284 KB |
Output is correct |
| 3 |
Correct |
116 ms |
62284 KB |
Output is correct |
| 4 |
Correct |
83 ms |
62284 KB |
Output is correct |
| 5 |
Execution timed out |
2000 ms |
62284 KB |
Execution timed out |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
62284 KB |
Output is correct |
| 2 |
Correct |
0 ms |
62284 KB |
Output is correct |
| 3 |
Correct |
116 ms |
62284 KB |
Output is correct |
| 4 |
Correct |
83 ms |
62284 KB |
Output is correct |
| 5 |
Execution timed out |
2000 ms |
62284 KB |
Execution timed out |
| 6 |
Halted |
0 ms |
0 KB |
- |
