# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
128845 |
2019-07-11T10:08:48 Z |
onjo0127 |
None (JOI16_ho_t4) |
C++11 |
|
68 ms |
48092 KB |
#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);
assert(N <= 90000);
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(x1[it.Y][it.X] >= 0);
}
}
reverse(T[i].begin(), T[i].end());
// 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(y[it.X] >= 0);
}
prv = RC(it);
}
else {
if(prv == INF) continue;
x2[it.Y][it.X] = day(prv, RC(it));
assert(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-le9, A[i].Y-le9, 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:29: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:85:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
23900 KB |
Output is correct |
2 |
Correct |
23 ms |
23848 KB |
Output is correct |
3 |
Correct |
23 ms |
23836 KB |
Output is correct |
4 |
Correct |
24 ms |
23800 KB |
Output is correct |
5 |
Correct |
23 ms |
23892 KB |
Output is correct |
6 |
Correct |
23 ms |
23800 KB |
Output is correct |
7 |
Correct |
24 ms |
23800 KB |
Output is correct |
8 |
Correct |
23 ms |
23800 KB |
Output is correct |
9 |
Correct |
45 ms |
23800 KB |
Output is correct |
10 |
Correct |
24 ms |
23848 KB |
Output is correct |
11 |
Correct |
31 ms |
23900 KB |
Output is correct |
12 |
Correct |
24 ms |
23932 KB |
Output is correct |
13 |
Correct |
24 ms |
23800 KB |
Output is correct |
14 |
Correct |
24 ms |
23900 KB |
Output is correct |
15 |
Correct |
24 ms |
23800 KB |
Output is correct |
16 |
Correct |
29 ms |
23908 KB |
Output is correct |
17 |
Correct |
32 ms |
23800 KB |
Output is correct |
18 |
Correct |
28 ms |
23924 KB |
Output is correct |
19 |
Correct |
24 ms |
23928 KB |
Output is correct |
20 |
Correct |
23 ms |
23804 KB |
Output is correct |
21 |
Correct |
23 ms |
23800 KB |
Output is correct |
22 |
Correct |
23 ms |
23872 KB |
Output is correct |
23 |
Correct |
24 ms |
23800 KB |
Output is correct |
24 |
Correct |
23 ms |
23800 KB |
Output is correct |
25 |
Correct |
24 ms |
23800 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
23900 KB |
Output is correct |
2 |
Correct |
23 ms |
23848 KB |
Output is correct |
3 |
Correct |
23 ms |
23836 KB |
Output is correct |
4 |
Correct |
24 ms |
23800 KB |
Output is correct |
5 |
Correct |
23 ms |
23892 KB |
Output is correct |
6 |
Correct |
23 ms |
23800 KB |
Output is correct |
7 |
Correct |
24 ms |
23800 KB |
Output is correct |
8 |
Correct |
23 ms |
23800 KB |
Output is correct |
9 |
Correct |
45 ms |
23800 KB |
Output is correct |
10 |
Correct |
24 ms |
23848 KB |
Output is correct |
11 |
Correct |
31 ms |
23900 KB |
Output is correct |
12 |
Correct |
24 ms |
23932 KB |
Output is correct |
13 |
Correct |
24 ms |
23800 KB |
Output is correct |
14 |
Correct |
24 ms |
23900 KB |
Output is correct |
15 |
Correct |
24 ms |
23800 KB |
Output is correct |
16 |
Correct |
29 ms |
23908 KB |
Output is correct |
17 |
Correct |
32 ms |
23800 KB |
Output is correct |
18 |
Correct |
28 ms |
23924 KB |
Output is correct |
19 |
Correct |
24 ms |
23928 KB |
Output is correct |
20 |
Correct |
23 ms |
23804 KB |
Output is correct |
21 |
Correct |
23 ms |
23800 KB |
Output is correct |
22 |
Correct |
23 ms |
23872 KB |
Output is correct |
23 |
Correct |
24 ms |
23800 KB |
Output is correct |
24 |
Correct |
23 ms |
23800 KB |
Output is correct |
25 |
Correct |
24 ms |
23800 KB |
Output is correct |
26 |
Correct |
24 ms |
23928 KB |
Output is correct |
27 |
Correct |
27 ms |
24164 KB |
Output is correct |
28 |
Correct |
27 ms |
24028 KB |
Output is correct |
29 |
Correct |
58 ms |
26748 KB |
Output is correct |
30 |
Correct |
68 ms |
26788 KB |
Output is correct |
31 |
Runtime error |
56 ms |
48092 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
32 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
23900 KB |
Output is correct |
2 |
Correct |
23 ms |
23848 KB |
Output is correct |
3 |
Correct |
23 ms |
23836 KB |
Output is correct |
4 |
Correct |
24 ms |
23800 KB |
Output is correct |
5 |
Correct |
23 ms |
23892 KB |
Output is correct |
6 |
Correct |
23 ms |
23800 KB |
Output is correct |
7 |
Correct |
24 ms |
23800 KB |
Output is correct |
8 |
Correct |
23 ms |
23800 KB |
Output is correct |
9 |
Correct |
45 ms |
23800 KB |
Output is correct |
10 |
Correct |
24 ms |
23848 KB |
Output is correct |
11 |
Correct |
31 ms |
23900 KB |
Output is correct |
12 |
Correct |
24 ms |
23932 KB |
Output is correct |
13 |
Correct |
24 ms |
23800 KB |
Output is correct |
14 |
Correct |
24 ms |
23900 KB |
Output is correct |
15 |
Correct |
24 ms |
23800 KB |
Output is correct |
16 |
Correct |
29 ms |
23908 KB |
Output is correct |
17 |
Correct |
32 ms |
23800 KB |
Output is correct |
18 |
Correct |
28 ms |
23924 KB |
Output is correct |
19 |
Correct |
24 ms |
23928 KB |
Output is correct |
20 |
Correct |
23 ms |
23804 KB |
Output is correct |
21 |
Correct |
23 ms |
23800 KB |
Output is correct |
22 |
Correct |
23 ms |
23872 KB |
Output is correct |
23 |
Correct |
24 ms |
23800 KB |
Output is correct |
24 |
Correct |
23 ms |
23800 KB |
Output is correct |
25 |
Correct |
24 ms |
23800 KB |
Output is correct |
26 |
Correct |
23 ms |
23928 KB |
Output is correct |
27 |
Correct |
24 ms |
23928 KB |
Output is correct |
28 |
Correct |
25 ms |
23928 KB |
Output is correct |
29 |
Correct |
29 ms |
23800 KB |
Output is correct |
30 |
Correct |
25 ms |
23928 KB |
Output is correct |
31 |
Correct |
25 ms |
23800 KB |
Output is correct |
32 |
Correct |
23 ms |
23932 KB |
Output is correct |
33 |
Correct |
25 ms |
23928 KB |
Output is correct |
34 |
Correct |
28 ms |
23676 KB |
Output is correct |
35 |
Correct |
26 ms |
23928 KB |
Output is correct |
36 |
Correct |
26 ms |
23928 KB |
Output is correct |
37 |
Correct |
26 ms |
23928 KB |
Output is correct |
38 |
Correct |
26 ms |
23928 KB |
Output is correct |
39 |
Correct |
25 ms |
23932 KB |
Output is correct |
40 |
Correct |
23 ms |
23928 KB |
Output is correct |
41 |
Correct |
26 ms |
23928 KB |
Output is correct |
42 |
Correct |
24 ms |
23780 KB |
Output is correct |
43 |
Correct |
25 ms |
23928 KB |
Output is correct |
44 |
Correct |
25 ms |
23928 KB |
Output is correct |
45 |
Correct |
25 ms |
23800 KB |
Output is correct |
46 |
Correct |
26 ms |
23928 KB |
Output is correct |
47 |
Correct |
30 ms |
23800 KB |
Output is correct |
48 |
Correct |
31 ms |
23928 KB |
Output is correct |
49 |
Correct |
26 ms |
23928 KB |
Output is correct |
50 |
Correct |
25 ms |
23932 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
23900 KB |
Output is correct |
2 |
Correct |
23 ms |
23848 KB |
Output is correct |
3 |
Correct |
23 ms |
23836 KB |
Output is correct |
4 |
Correct |
24 ms |
23800 KB |
Output is correct |
5 |
Correct |
23 ms |
23892 KB |
Output is correct |
6 |
Correct |
23 ms |
23800 KB |
Output is correct |
7 |
Correct |
24 ms |
23800 KB |
Output is correct |
8 |
Correct |
23 ms |
23800 KB |
Output is correct |
9 |
Correct |
45 ms |
23800 KB |
Output is correct |
10 |
Correct |
24 ms |
23848 KB |
Output is correct |
11 |
Correct |
31 ms |
23900 KB |
Output is correct |
12 |
Correct |
24 ms |
23932 KB |
Output is correct |
13 |
Correct |
24 ms |
23800 KB |
Output is correct |
14 |
Correct |
24 ms |
23900 KB |
Output is correct |
15 |
Correct |
24 ms |
23800 KB |
Output is correct |
16 |
Correct |
29 ms |
23908 KB |
Output is correct |
17 |
Correct |
32 ms |
23800 KB |
Output is correct |
18 |
Correct |
28 ms |
23924 KB |
Output is correct |
19 |
Correct |
24 ms |
23928 KB |
Output is correct |
20 |
Correct |
23 ms |
23804 KB |
Output is correct |
21 |
Correct |
23 ms |
23800 KB |
Output is correct |
22 |
Correct |
23 ms |
23872 KB |
Output is correct |
23 |
Correct |
24 ms |
23800 KB |
Output is correct |
24 |
Correct |
23 ms |
23800 KB |
Output is correct |
25 |
Correct |
24 ms |
23800 KB |
Output is correct |
26 |
Correct |
24 ms |
23928 KB |
Output is correct |
27 |
Correct |
27 ms |
24164 KB |
Output is correct |
28 |
Correct |
27 ms |
24028 KB |
Output is correct |
29 |
Correct |
58 ms |
26748 KB |
Output is correct |
30 |
Correct |
68 ms |
26788 KB |
Output is correct |
31 |
Runtime error |
56 ms |
48092 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
32 |
Halted |
0 ms |
0 KB |
- |