#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using pli = pair<long long, int>;
using tiii = tuple<int, int, int>;
#define X first
#define Y second
const int le9 = 1e9;
const pii INF = {-1e9, -1e9};
pii df; int dx, dy;
int N, K, P[1000009];
int x1[4][1000009], x2[4][1000009], y[1000009];
char S[1000009];
set<pii> st;
void mv(pii &CR, char c) {
if(c == 'S') --CR.Y;
if(c == 'N') ++CR.Y;
if(c == 'W') --CR.X;
if(c == 'E') ++CR.X;
}
void input() {
scanf("%d%d",&N,&K);
for(int i=1; i<=N; i++) {
scanf(" %c", &S[i]);
mv(df, S[i]);
}
if(df.X < 0) {
df.X = -df.X;
for(int i=1; i<=N; i++) {
if(S[i] == 'W') S[i] = 'E';
else if(S[i] == 'E') S[i] = 'W';
}
}
if(df.Y < 0) {
df.Y = -df.Y;
for(int i=1; i<=N; i++) {
if(S[i] == 'N') S[i] = 'S';
else if(S[i] == 'S') S[i] = 'N';
}
}
}
void go(pii &now) {
st.insert(now);
for(int i=1; i<=N; i++) {
mv(now, S[i]);
st.insert(now);
}
}
int cnt() {
int ret = 0;
for(auto& it: st) {
int c = 0;
if(st.find({it.X+1, it.Y}) != st.end()) ++c;
if(st.find({it.X, it.Y+1}) != st.end()) ++c;
if(st.find({it.X+1, it.Y+1}) != st.end()) ++c;
if(c == 3) ++ret;
}
return ret;
}
pli geti(pii A) {
if(dx == 0) return {A.X, A.Y % dy};
if(dy == 0) return {A.Y, A.X % dx};
return {1LL * A.X * dy - 1LL * A.Y * dx, A.Y % dy};
}
int day(pii A, pii B) {
return (dx ? (A.X - B.X) / dx : (A.Y - B.Y) / dy) + 1;
}
vector<pii> A;
pii RC(pii U) {
if(U.Y == 0) return A[U.X];
if(U.Y == 1) return {A[U.X].X+1, A[U.X].Y};
if(U.Y == 2) return {A[U.X].X, A[U.X].Y+1};
if(U.Y == 3) return {A[U.X].X+1, A[U.X].Y+1};
}
vector<pii> T[1000009];
int main() {
input(); tie(dx, dy) = df;
pii now = {100000, 100000}; go(now);
// printf("dx: %d, dy: %d\n", dx, dy);
if(dx == 0 && dy == 0) return !printf("%d", cnt());
map<pli, int> id; int M = 0;
for(auto& it: st) {
if(id[geti(it)] == 0) id[geti(it)] = ++M;
if(id[geti({it.X+1, it.Y})] == 0) id[geti({it.X+1, it.Y})] = ++M;
if(id[geti({it.X, it.Y+1})] == 0) id[geti({it.X, it.Y+1})] = ++M;
if(id[geti({it.X+1, it.Y+1})] == 0) id[geti({it.X+1, it.Y+1})] = ++M;
}
for(auto& it: st) {
T[id[geti(it)]].push_back({A.size(), 0});
T[id[geti({it.X+1, it.Y})]].push_back({A.size(), 1});
T[id[geti({it.X, it.Y+1})]].push_back({A.size(), 2});
T[id[geti({it.X+1, it.Y+1})]].push_back({A.size(), 3});
A.push_back(it);
}
int E = A.size();
for(int i=1; i<=M; i++) {
sort(T[i].begin(), T[i].end(), [&](pii PP, pii QQ) {
if(RC(PP) == RC(QQ)) return PP.Y < QQ.Y;
return RC(PP) < RC(QQ);
});
// for(auto& it: T[i]) printf("Ai: %d, (%d, %d), type: %d\n", it.X, RC(it).X - le9, RC(it).Y - le9, it.Y);
// puts("------------------");
// calculate x1
pii prv = INF;
for(auto& it: T[i]) {
if(it.Y == 0) prv = RC(it);
else {
if(prv == INF) continue;
x1[it.Y][it.X] = day(RC(it), prv);
assert(N >= x1[it.Y][it.X] && x1[it.Y][it.X] >= 1);
}
}
sort(T[i].begin(), T[i].end(), [&](pii PP, pii QQ) {
if(RC(PP) == RC(QQ)) return PP.Y < QQ.Y;
return RC(PP) > RC(QQ);
});
// calculate x2 and y
prv = INF;
for(auto& it: T[i]) {
if(it.Y == 0) {
if(prv != INF) {
y[it.X] = day(prv, RC(it));
assert(N >= y[it.X] && y[it.X] >= 1);
}
prv = RC(it);
}
else {
if(prv == INF) continue;
x2[it.Y][it.X] = day(prv, RC(it));
assert(x2[it.Y][it.X] <= N && x2[it.Y][it.X] >= 0);
}
}
}
int inf = 1000000;
for(int i=0; i<E; i++) {
int X1 = 2*inf, X2 = 2*inf, Y = 2*inf;
if(x1[1][i] && x1[2][i] && x1[3][i]) X1 = max({x1[1][i], x1[2][i], x1[3][i]});
if(x2[1][i] && x2[2][i] && x2[3][i]) X2 = max({x2[1][i], x2[2][i], x2[3][i]});
if(y[i]) Y = y[i];
int s1 = X1, e1 = X1 + Y - 2;
int s2 = X2, e2 = Y - 1;
e1 = min(e1, X1 + X2 - 2);
s1 = min(s1, inf);
e1 = min(e1, inf);
s2 = min(s2, inf);
e2 = min(e2, inf);
if(s1 <= e1) ++P[s1], --P[e1+1];
if(s2 <= e2) ++P[s2], --P[e2+1];
// printf("i: %d, (%d, %d), x1: %d, x2: %d, y: %d, [%d, %d], [%d, %d]\n", i, A[i].X-100000, A[i].Y-100000, X1, X2, Y, s1, e1, s2, e2);
}
long long ds = 0, sum = 0;
for(int i=1; i<inf; i++) {
ds += P[i];
sum += ds;
if(i == K) {
return !printf("%lld", sum);
}
}
printf("%lld", sum + ds*(K-inf+1));
return 0;
}
Compilation message
2016_ho_t4.cpp: In function 'void input()':
2016_ho_t4.cpp:26:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&N,&K);
~~~~~^~~~~~~~~~~~~~
2016_ho_t4.cpp:28:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c", &S[i]);
~~~~~^~~~~~~~~~~~~~
2016_ho_t4.cpp: In function 'pii RC(pii)':
2016_ho_t4.cpp:84:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
24 ms |
23800 KB |
Output is correct |
2 |
Correct |
24 ms |
23772 KB |
Output is correct |
3 |
Correct |
24 ms |
23900 KB |
Output is correct |
4 |
Correct |
24 ms |
23864 KB |
Output is correct |
5 |
Correct |
24 ms |
23864 KB |
Output is correct |
6 |
Correct |
24 ms |
23800 KB |
Output is correct |
7 |
Correct |
24 ms |
23804 KB |
Output is correct |
8 |
Correct |
23 ms |
23800 KB |
Output is correct |
9 |
Correct |
23 ms |
23928 KB |
Output is correct |
10 |
Correct |
24 ms |
23800 KB |
Output is correct |
11 |
Correct |
23 ms |
23928 KB |
Output is correct |
12 |
Correct |
23 ms |
23800 KB |
Output is correct |
13 |
Correct |
23 ms |
23800 KB |
Output is correct |
14 |
Correct |
24 ms |
23928 KB |
Output is correct |
15 |
Correct |
24 ms |
23800 KB |
Output is correct |
16 |
Correct |
23 ms |
23800 KB |
Output is correct |
17 |
Correct |
23 ms |
23928 KB |
Output is correct |
18 |
Correct |
23 ms |
23800 KB |
Output is correct |
19 |
Correct |
24 ms |
23800 KB |
Output is correct |
20 |
Correct |
27 ms |
23800 KB |
Output is correct |
21 |
Correct |
24 ms |
23852 KB |
Output is correct |
22 |
Correct |
23 ms |
23800 KB |
Output is correct |
23 |
Correct |
23 ms |
23892 KB |
Output is correct |
24 |
Correct |
24 ms |
23928 KB |
Output is correct |
25 |
Correct |
28 ms |
23800 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
24 ms |
23800 KB |
Output is correct |
2 |
Correct |
24 ms |
23772 KB |
Output is correct |
3 |
Correct |
24 ms |
23900 KB |
Output is correct |
4 |
Correct |
24 ms |
23864 KB |
Output is correct |
5 |
Correct |
24 ms |
23864 KB |
Output is correct |
6 |
Correct |
24 ms |
23800 KB |
Output is correct |
7 |
Correct |
24 ms |
23804 KB |
Output is correct |
8 |
Correct |
23 ms |
23800 KB |
Output is correct |
9 |
Correct |
23 ms |
23928 KB |
Output is correct |
10 |
Correct |
24 ms |
23800 KB |
Output is correct |
11 |
Correct |
23 ms |
23928 KB |
Output is correct |
12 |
Correct |
23 ms |
23800 KB |
Output is correct |
13 |
Correct |
23 ms |
23800 KB |
Output is correct |
14 |
Correct |
24 ms |
23928 KB |
Output is correct |
15 |
Correct |
24 ms |
23800 KB |
Output is correct |
16 |
Correct |
23 ms |
23800 KB |
Output is correct |
17 |
Correct |
23 ms |
23928 KB |
Output is correct |
18 |
Correct |
23 ms |
23800 KB |
Output is correct |
19 |
Correct |
24 ms |
23800 KB |
Output is correct |
20 |
Correct |
27 ms |
23800 KB |
Output is correct |
21 |
Correct |
24 ms |
23852 KB |
Output is correct |
22 |
Correct |
23 ms |
23800 KB |
Output is correct |
23 |
Correct |
23 ms |
23892 KB |
Output is correct |
24 |
Correct |
24 ms |
23928 KB |
Output is correct |
25 |
Correct |
28 ms |
23800 KB |
Output is correct |
26 |
Correct |
23 ms |
23900 KB |
Output is correct |
27 |
Correct |
27 ms |
24092 KB |
Output is correct |
28 |
Correct |
27 ms |
24040 KB |
Output is correct |
29 |
Correct |
60 ms |
26972 KB |
Output is correct |
30 |
Correct |
65 ms |
26808 KB |
Output is correct |
31 |
Correct |
266 ms |
45216 KB |
Output is correct |
32 |
Correct |
48 ms |
24924 KB |
Output is correct |
33 |
Correct |
93 ms |
29268 KB |
Output is correct |
34 |
Correct |
99 ms |
29684 KB |
Output is correct |
35 |
Correct |
106 ms |
28960 KB |
Output is correct |
36 |
Correct |
75 ms |
27764 KB |
Output is correct |
37 |
Correct |
55 ms |
25080 KB |
Output is correct |
38 |
Correct |
91 ms |
28660 KB |
Output is correct |
39 |
Correct |
84 ms |
29064 KB |
Output is correct |
40 |
Correct |
48 ms |
24952 KB |
Output is correct |
41 |
Correct |
80 ms |
27040 KB |
Output is correct |
42 |
Correct |
77 ms |
27128 KB |
Output is correct |
43 |
Correct |
105 ms |
29104 KB |
Output is correct |
44 |
Correct |
89 ms |
28788 KB |
Output is correct |
45 |
Correct |
77 ms |
28016 KB |
Output is correct |
46 |
Correct |
138 ms |
31472 KB |
Output is correct |
47 |
Correct |
154 ms |
33128 KB |
Output is correct |
48 |
Correct |
294 ms |
35972 KB |
Output is correct |
49 |
Correct |
356 ms |
49128 KB |
Output is correct |
50 |
Correct |
358 ms |
49132 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
24 ms |
23800 KB |
Output is correct |
2 |
Correct |
24 ms |
23772 KB |
Output is correct |
3 |
Correct |
24 ms |
23900 KB |
Output is correct |
4 |
Correct |
24 ms |
23864 KB |
Output is correct |
5 |
Correct |
24 ms |
23864 KB |
Output is correct |
6 |
Correct |
24 ms |
23800 KB |
Output is correct |
7 |
Correct |
24 ms |
23804 KB |
Output is correct |
8 |
Correct |
23 ms |
23800 KB |
Output is correct |
9 |
Correct |
23 ms |
23928 KB |
Output is correct |
10 |
Correct |
24 ms |
23800 KB |
Output is correct |
11 |
Correct |
23 ms |
23928 KB |
Output is correct |
12 |
Correct |
23 ms |
23800 KB |
Output is correct |
13 |
Correct |
23 ms |
23800 KB |
Output is correct |
14 |
Correct |
24 ms |
23928 KB |
Output is correct |
15 |
Correct |
24 ms |
23800 KB |
Output is correct |
16 |
Correct |
23 ms |
23800 KB |
Output is correct |
17 |
Correct |
23 ms |
23928 KB |
Output is correct |
18 |
Correct |
23 ms |
23800 KB |
Output is correct |
19 |
Correct |
24 ms |
23800 KB |
Output is correct |
20 |
Correct |
27 ms |
23800 KB |
Output is correct |
21 |
Correct |
24 ms |
23852 KB |
Output is correct |
22 |
Correct |
23 ms |
23800 KB |
Output is correct |
23 |
Correct |
23 ms |
23892 KB |
Output is correct |
24 |
Correct |
24 ms |
23928 KB |
Output is correct |
25 |
Correct |
28 ms |
23800 KB |
Output is correct |
26 |
Correct |
27 ms |
23928 KB |
Output is correct |
27 |
Correct |
24 ms |
23800 KB |
Output is correct |
28 |
Correct |
27 ms |
23928 KB |
Output is correct |
29 |
Correct |
24 ms |
23932 KB |
Output is correct |
30 |
Correct |
23 ms |
23804 KB |
Output is correct |
31 |
Correct |
26 ms |
23928 KB |
Output is correct |
32 |
Correct |
24 ms |
23904 KB |
Output is correct |
33 |
Correct |
26 ms |
23928 KB |
Output is correct |
34 |
Correct |
23 ms |
23932 KB |
Output is correct |
35 |
Correct |
25 ms |
23928 KB |
Output is correct |
36 |
Correct |
26 ms |
23928 KB |
Output is correct |
37 |
Correct |
26 ms |
23888 KB |
Output is correct |
38 |
Correct |
26 ms |
23928 KB |
Output is correct |
39 |
Correct |
25 ms |
23928 KB |
Output is correct |
40 |
Correct |
23 ms |
23800 KB |
Output is correct |
41 |
Correct |
26 ms |
23928 KB |
Output is correct |
42 |
Correct |
24 ms |
23800 KB |
Output is correct |
43 |
Correct |
26 ms |
23928 KB |
Output is correct |
44 |
Correct |
26 ms |
23800 KB |
Output is correct |
45 |
Correct |
25 ms |
23932 KB |
Output is correct |
46 |
Correct |
25 ms |
23928 KB |
Output is correct |
47 |
Correct |
25 ms |
23928 KB |
Output is correct |
48 |
Correct |
25 ms |
23928 KB |
Output is correct |
49 |
Correct |
25 ms |
23928 KB |
Output is correct |
50 |
Correct |
25 ms |
23928 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
24 ms |
23800 KB |
Output is correct |
2 |
Correct |
24 ms |
23772 KB |
Output is correct |
3 |
Correct |
24 ms |
23900 KB |
Output is correct |
4 |
Correct |
24 ms |
23864 KB |
Output is correct |
5 |
Correct |
24 ms |
23864 KB |
Output is correct |
6 |
Correct |
24 ms |
23800 KB |
Output is correct |
7 |
Correct |
24 ms |
23804 KB |
Output is correct |
8 |
Correct |
23 ms |
23800 KB |
Output is correct |
9 |
Correct |
23 ms |
23928 KB |
Output is correct |
10 |
Correct |
24 ms |
23800 KB |
Output is correct |
11 |
Correct |
23 ms |
23928 KB |
Output is correct |
12 |
Correct |
23 ms |
23800 KB |
Output is correct |
13 |
Correct |
23 ms |
23800 KB |
Output is correct |
14 |
Correct |
24 ms |
23928 KB |
Output is correct |
15 |
Correct |
24 ms |
23800 KB |
Output is correct |
16 |
Correct |
23 ms |
23800 KB |
Output is correct |
17 |
Correct |
23 ms |
23928 KB |
Output is correct |
18 |
Correct |
23 ms |
23800 KB |
Output is correct |
19 |
Correct |
24 ms |
23800 KB |
Output is correct |
20 |
Correct |
27 ms |
23800 KB |
Output is correct |
21 |
Correct |
24 ms |
23852 KB |
Output is correct |
22 |
Correct |
23 ms |
23800 KB |
Output is correct |
23 |
Correct |
23 ms |
23892 KB |
Output is correct |
24 |
Correct |
24 ms |
23928 KB |
Output is correct |
25 |
Correct |
28 ms |
23800 KB |
Output is correct |
26 |
Correct |
23 ms |
23900 KB |
Output is correct |
27 |
Correct |
27 ms |
24092 KB |
Output is correct |
28 |
Correct |
27 ms |
24040 KB |
Output is correct |
29 |
Correct |
60 ms |
26972 KB |
Output is correct |
30 |
Correct |
65 ms |
26808 KB |
Output is correct |
31 |
Correct |
266 ms |
45216 KB |
Output is correct |
32 |
Correct |
48 ms |
24924 KB |
Output is correct |
33 |
Correct |
93 ms |
29268 KB |
Output is correct |
34 |
Correct |
99 ms |
29684 KB |
Output is correct |
35 |
Correct |
106 ms |
28960 KB |
Output is correct |
36 |
Correct |
75 ms |
27764 KB |
Output is correct |
37 |
Correct |
55 ms |
25080 KB |
Output is correct |
38 |
Correct |
91 ms |
28660 KB |
Output is correct |
39 |
Correct |
84 ms |
29064 KB |
Output is correct |
40 |
Correct |
48 ms |
24952 KB |
Output is correct |
41 |
Correct |
80 ms |
27040 KB |
Output is correct |
42 |
Correct |
77 ms |
27128 KB |
Output is correct |
43 |
Correct |
105 ms |
29104 KB |
Output is correct |
44 |
Correct |
89 ms |
28788 KB |
Output is correct |
45 |
Correct |
77 ms |
28016 KB |
Output is correct |
46 |
Correct |
138 ms |
31472 KB |
Output is correct |
47 |
Correct |
154 ms |
33128 KB |
Output is correct |
48 |
Correct |
294 ms |
35972 KB |
Output is correct |
49 |
Correct |
356 ms |
49128 KB |
Output is correct |
50 |
Correct |
358 ms |
49132 KB |
Output is correct |
51 |
Correct |
27 ms |
23928 KB |
Output is correct |
52 |
Correct |
24 ms |
23800 KB |
Output is correct |
53 |
Correct |
27 ms |
23928 KB |
Output is correct |
54 |
Correct |
24 ms |
23932 KB |
Output is correct |
55 |
Correct |
23 ms |
23804 KB |
Output is correct |
56 |
Correct |
26 ms |
23928 KB |
Output is correct |
57 |
Correct |
24 ms |
23904 KB |
Output is correct |
58 |
Correct |
26 ms |
23928 KB |
Output is correct |
59 |
Correct |
23 ms |
23932 KB |
Output is correct |
60 |
Correct |
25 ms |
23928 KB |
Output is correct |
61 |
Correct |
26 ms |
23928 KB |
Output is correct |
62 |
Correct |
26 ms |
23888 KB |
Output is correct |
63 |
Correct |
26 ms |
23928 KB |
Output is correct |
64 |
Correct |
25 ms |
23928 KB |
Output is correct |
65 |
Correct |
23 ms |
23800 KB |
Output is correct |
66 |
Correct |
26 ms |
23928 KB |
Output is correct |
67 |
Correct |
24 ms |
23800 KB |
Output is correct |
68 |
Correct |
26 ms |
23928 KB |
Output is correct |
69 |
Correct |
26 ms |
23800 KB |
Output is correct |
70 |
Correct |
25 ms |
23932 KB |
Output is correct |
71 |
Correct |
25 ms |
23928 KB |
Output is correct |
72 |
Correct |
25 ms |
23928 KB |
Output is correct |
73 |
Correct |
25 ms |
23928 KB |
Output is correct |
74 |
Correct |
25 ms |
23928 KB |
Output is correct |
75 |
Correct |
25 ms |
23928 KB |
Output is correct |
76 |
Correct |
29 ms |
24184 KB |
Output is correct |
77 |
Correct |
25 ms |
23928 KB |
Output is correct |
78 |
Correct |
73 ms |
27084 KB |
Output is correct |
79 |
Correct |
154 ms |
36052 KB |
Output is correct |
80 |
Incorrect |
78 ms |
27252 KB |
Output isn't correct |
81 |
Halted |
0 ms |
0 KB |
- |