oj.uz

Submission #569403

# Submission time Handle Problem Language Result Execution time Memory
569403 2022-05-27T11:22:17 Z Ooops_sorry Land of the Rainbow Gold (APIO17_rainbow) C++14
11 / 100
 3000 ms 162640 KB 
#include<bits/stdc++.h>
#ifndef LOCAL
    #include "rainbow.h"
#endif // LCOAL

using namespace std;

#define pb push_back
#define ld double
#define ll long long

mt19937 rnd(51);

set<pair<int,int>> st;
vector<pair<int,int>> d{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

void init(int r, int c, int sr, int sc, int m, char *s) {
    st.clear();
    sr--, sc--;
    st.insert({sr, sc});
    for (int i = 0; i < m; i++) {
        if (s[i] == 'N') {
            sr--;
        } else if (s[i] == 'S') {
            sr++;
        } else if (s[i] == 'W') {
            sc--;
        } else {
            sc++;
        }
        assert(0 <= sr && sr < r && 0 <= sc && sc < c);
        st.insert({sr, sc});
    }
}

bool check(int i, int j) {
    return (st.find({i, j}) != st.end());
}

int solve(int ar, int ac, int br, int bc) {
    ar--, ac--, br--, bc--;
    ll n = 0, m = 0, s = 0;
    for (int i = ar; i <= br; i++) {
        for (int j = ac; j <= bc; j++) {
            if (check(i, j)) {
                n++;
                if (i + 1 <= br && check(i + 1, j)) {
                    m++;
                }
                if (j + 1 <= bc && check(i, j + 1)) {
                    m++;
                }
                if (i + 1 <= br && j + 1 <= bc && check(i + 1, j + 1) && check(i, j + 1) && check(i + 1, j)) {
                    s++;
                }
            }
        }
    }
    if (n == (ll)(br - ar + 1) * (bc - ac + 1)) {
        return 0;
    }
    int cnt = 0;
    for (int i = ar; i <= br; i++) {
        if (check(i, ac)) {
            cnt++;
            if (i + 1 <= br && check(i + 1, ac)) {
                s++;
            }
        }
        if (check(i, bc)) {
            cnt++;
            if (i + 1 <= br && check(i + 1, bc)) {
                s++;
            }
        }
    }
    for (int j = ac; j < bc; j++) {
        if (check(ar, j)) {
            if (j > ac) cnt++;
            if (j + 1 <= bc && check(ar, j + 1)) {
                s++;
            }
        }
        if (check(br, j)) {
            if (j > ac) cnt++;
            if (j + 1 <= bc && check(br, j + 1)) {
                s++;
            }
        }
    }
    if (cnt == 0) {
        if (n == 0) {
            return 1;
        } else {
            return 2 + m - n;
        }
    } else {
        m += cnt;
        return 1 + m - n - s;
    }
}

int colour(int ar, int ac, int br, int bc) {
    ar--, ac--, br--, bc--;
    map<pair<int,int>, int> used;
    int cnt = 0;
    for (int i = ar; i <= br; i++) {
        for (int j = ac; j <= bc; j++) {
            if (!check(i, j) && !used[{i, j}]) {
                cnt++;
                used[{i, j}] = 1;
                deque<pair<int,int>> q{{i, j}};
                while (q.size() > 0) {
                    int f = q.front().first, s = q.front().second;
                    q.pop_front();
                    for (auto to : d) {
                        f += to.first, s += to.second;
                        if (ar <= f && f <= br && ac <= s && s <= bc) {
                            if (!used[{f, s}] && !check(f, s)) {
                                q.pb({f, s});
                                used[{f, s}] = 1;
                            }
                        }
                        f -= to.first, s -= to.second;
                    }
                }
            }
        }
    }
    return cnt;
}

#ifdef LOCAL

static int R, C, M, Q;
static int sr, sc;
static char S[100000 + 5];

int main() {
    scanf("%d %d %d %d", &R, &C, &M, &Q);
    scanf("%d %d", &sr, &sc);
    if (M > 0) {
        scanf(" %s ", S);
    }

    init(R, C, sr, sc, M, S);

    int query;
    for (query = 0; query < Q; query++) {
        int ar, ac, br, bc;
        scanf("%d %d %d %d", &ar, &ac, &br, &bc);
        printf("%d\n", colour(ar, ac, br, bc));
    }

    return 0;
}

#endif // LOCAL

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 340 KB Output is correct
2 Correct 120 ms 496 KB Output is correct
3 Correct 322 ms 616 KB Output is correct
4 Correct 358 ms 468 KB Output is correct
5 Correct 112 ms 528 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 290 ms 492 KB Output is correct
12 Correct 210 ms 468 KB Output is correct
13 Correct 236 ms 520 KB Output is correct
14 Correct 183 ms 528 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Execution timed out 3090 ms 22312 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 3102 ms 162640 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 340 KB Output is correct
2 Correct 120 ms 496 KB Output is correct
3 Correct 322 ms 616 KB Output is correct
4 Correct 358 ms 468 KB Output is correct
5 Correct 112 ms 528 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 290 ms 492 KB Output is correct
12 Correct 210 ms 468 KB Output is correct
13 Correct 236 ms 520 KB Output is correct
14 Correct 183 ms 528 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Execution timed out 3089 ms 39044 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 340 KB Output is correct
2 Correct 120 ms 496 KB Output is correct
3 Correct 322 ms 616 KB Output is correct
4 Correct 358 ms 468 KB Output is correct
5 Correct 112 ms 528 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 290 ms 492 KB Output is correct
12 Correct 210 ms 468 KB Output is correct
13 Correct 236 ms 520 KB Output is correct
14 Correct 183 ms 528 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Execution timed out 3089 ms 39044 KB Time limit exceeded
19 Halted 0 ms 0 KB -