| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 521815 |
2022-02-03T08:29:59 Z |
ntabc05101 |
Ruka (COI15_ruka) |
C++14 |
|
1106 ms |
30940 KB |
#include<bits/stdc++.h>
using namespace std;
#define taskname ""
const int mxN = 100005;
const int off_set = 5e7;
const int mxX = 1e8 + 5;
int n, m;
int x[mxN], y[mxN], sumx, sumy;
int crl;
struct BIT {
unordered_map<int, int> bits;
void upd(int x, int dlt) {
for (x += off_set; x < mxX; x += x & -x) {
bits[x] += dlt;
}
}
int get(int x) {
int res = 0;
for (x += off_set; x; x &= x - 1) {
res += bits[x];
}
return res;
}
} pLx, pHx, sLx, sHx, pLy, pHy, sLy, sHy;
void upd(BIT &L, BIT &H, int a, int b, int dlt) {
if (a < b) {
swap(a, b);
}
L.upd(b, dlt);
H.upd(a, dlt);
}
void build(int x[], BIT &pL, BIT &pH, BIT &sL, BIT &sH) {
for (int i = 1; i < 2; i++) {
x[i] += x[i - 1];
upd(pL, pH, x[i], x[i - 1], 1);
}
for (int i = 2, a, b; i <= n; i++) {
x[i] += x[i - 1];
upd(sL, sH, x[i], x[i - 1], 1);
}
/*for (int i = n; i; i--) {
x[i] -= x[i - 1];
}*/
}
void bck() {
if (crl > 1) {
upd(pLx, pHx, x[crl], x[crl - 1], -1);
upd(pLy, pHy, y[crl], y[crl - 1], -1);
x[crl] -= sumx; y[crl] -= sumy;
upd(sLx, sHx, x[crl], x[crl - 1] - sumx, 1);
upd(sLy, sHy, y[crl], y[crl - 1] - sumy, 1);
crl--;
}
}
void frt() {
if (crl < n) {
crl++;
x[crl] += sumx; y[crl] += sumy;
upd(pLx, pHx, x[crl], x[crl - 1], 1);
upd(pLy, pHy, y[crl], y[crl - 1], 1);
upd(sLx, sHx, x[crl] - sumx, x[crl - 1] - sumx, -1);
upd(sLy, sHy, y[crl] - sumy, y[crl - 1] - sumy, -1);
}
}
int main() {
if (fopen(taskname".inp", "r")) {
freopen(taskname".inp", "r", stdin);
freopen(taskname".out", "w", stdout);
}
else {
if (fopen(taskname".in", "r")) {
freopen(taskname".in", "r", stdin);
freopen(taskname".out", "w", stdout);
}
}
cin.tie(0)->sync_with_stdio(0);
cin >> n;
x[0] = y[0] = 1;
for (int i = 1; i <= n; i++) {
cin >> x[i] >> y[i];
}
build(x, pLx, pHx, sLx, sHx);
build(y, pLy, pHy, sLy, sHy);
cin >> m;
crl = 1;
char c; int X, Y;
while (m--) {
cin >> c;
if (c == 'B') {
bck();
}
else {
if (c == 'F') {
frt();
}
else {
if (c == 'C') {
cin >> X >> Y;
upd(pLx, pHx, x[crl], x[crl - 1], -1);
upd(pLy, pHy, y[crl], y[crl - 1], -1);
if (crl < n) {
upd(sLx, sHx, x[crl + 1], x[crl] - sumx, -1);
upd(sLy, sHy, y[crl + 1], y[crl] - sumy, -1);
}
sumx += X - x[crl] + x[crl - 1];
sumy += Y - y[crl] + y[crl - 1];
x[crl] = x[crl - 1] + X;
y[crl] = y[crl - 1] + Y;
upd(pLx, pHx, x[crl], x[crl - 1], 1);
upd(pLy, pHy, y[crl], y[crl - 1], 1);
if (crl < n) {
upd(sLx, sHx, x[crl + 1], x[crl] - sumx, 1);
upd(sLy, sHy, y[crl + 1], y[crl] - sumy, 1);
}
}
else {
cout << sLx.get(-sumx) - sHx.get(-sumx) + pLx.get(0) - pHx.get(0) + sLy.get(-sumy) - sHy.get(-sumy) + pLy.get(0) - pHy.get(0) << "\n";
}
}
}
}
return 0;
}
Compilation message
ruka.cpp: In function 'void build(int*, BIT&, BIT&, BIT&, BIT&)':
ruka.cpp:45:18: warning: unused variable 'a' [-Wunused-variable]
45 | for (int i = 2, a, b; i <= n; i++) {
| ^
ruka.cpp:45:21: warning: unused variable 'b' [-Wunused-variable]
45 | for (int i = 2, a, b; i <= n; i++) {
| ^
ruka.cpp: In function 'int main()':
ruka.cpp:78:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
78 | freopen(taskname".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
ruka.cpp:79:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
79 | freopen(taskname".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ruka.cpp:83:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
83 | freopen(taskname".in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
ruka.cpp:84:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
84 | freopen(taskname".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
588 KB |
Output is correct |
| 2 |
Correct |
4 ms |
596 KB |
Output is correct |
| 3 |
Correct |
5 ms |
716 KB |
Output is correct |
| 4 |
Correct |
4 ms |
460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
588 KB |
Output is correct |
| 2 |
Correct |
4 ms |
596 KB |
Output is correct |
| 3 |
Correct |
5 ms |
716 KB |
Output is correct |
| 4 |
Correct |
4 ms |
460 KB |
Output is correct |
| 5 |
Correct |
368 ms |
13396 KB |
Output is correct |
| 6 |
Correct |
341 ms |
11416 KB |
Output is correct |
| 7 |
Correct |
356 ms |
9528 KB |
Output is correct |
| 8 |
Correct |
347 ms |
9904 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
588 KB |
Output is correct |
| 2 |
Correct |
4 ms |
596 KB |
Output is correct |
| 3 |
Correct |
5 ms |
716 KB |
Output is correct |
| 4 |
Correct |
4 ms |
460 KB |
Output is correct |
| 5 |
Correct |
368 ms |
13396 KB |
Output is correct |
| 6 |
Correct |
341 ms |
11416 KB |
Output is correct |
| 7 |
Correct |
356 ms |
9528 KB |
Output is correct |
| 8 |
Correct |
347 ms |
9904 KB |
Output is correct |
| 9 |
Correct |
1054 ms |
27288 KB |
Output is correct |
| 10 |
Correct |
1106 ms |
30940 KB |
Output is correct |
| 11 |
Correct |
933 ms |
26312 KB |
Output is correct |
| 12 |
Correct |
923 ms |
22692 KB |
Output is correct |
