| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 27301 |
2017-07-12T07:25:31 Z |
윤교준(#1144) |
Ruka (COI15_ruka) |
C++11 |
|
2000 ms |
8348 KB |
#include <bits/stdc++.h>
#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 (333)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
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[SQN*2+5], S[SQN*2+5];
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() {
scanf("%d", &N);
X[1] = Y[1] = 1; for(int i = 1; i <= N; i++) {
int dx, dy; scanf("%d%d", &dx, &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]);
}
initNode();
for(scanf("%d", &M); M--;) {
char c; scanf(" %c", &c);
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; scanf("%d%d", &dx, &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);
}
}
return 0;
}
Compilation message
ruka.cpp: In function 'int main()':
ruka.cpp:105:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
^
ruka.cpp:107:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int dx, dy; scanf("%d%d", &dx, &dy);
^
ruka.cpp:115:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(scanf("%d", &M); M--;) {
^
ruka.cpp:116:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
char c; scanf(" %c", &c);
^
ruka.cpp:121:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int dx, dy; scanf("%d%d", &dx, &dy);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
8348 KB |
Output is correct |
| 2 |
Correct |
3 ms |
8348 KB |
Output is correct |
| 3 |
Correct |
113 ms |
8348 KB |
Output is correct |
| 4 |
Correct |
86 ms |
8348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
8348 KB |
Output is correct |
| 2 |
Correct |
3 ms |
8348 KB |
Output is correct |
| 3 |
Correct |
113 ms |
8348 KB |
Output is correct |
| 4 |
Correct |
86 ms |
8348 KB |
Output is correct |
| 5 |
Execution timed out |
2000 ms |
8348 KB |
Execution timed out |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
8348 KB |
Output is correct |
| 2 |
Correct |
3 ms |
8348 KB |
Output is correct |
| 3 |
Correct |
113 ms |
8348 KB |
Output is correct |
| 4 |
Correct |
86 ms |
8348 KB |
Output is correct |
| 5 |
Execution timed out |
2000 ms |
8348 KB |
Execution timed out |
| 6 |
Halted |
0 ms |
0 KB |
- |
