제출 #569403

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
569403		Ooops_sorry	무지개나라 (APIO17_rainbow)	C++14	11 / 100	3102 ms	162640 KiB

rainbow

#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 / 11
• Subtask 2: 0 / 12
• Subtask 3: 0 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26