Submission #569422

#	Time	Username	Problem	Language	Result	Execution time	Memory
569422		Ooops_sorry	Land of the Rainbow Gold (APIO17_rainbow)	C++14	0 / 100	3042 ms	5068 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 colour(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)) {
            cnt++;
            if (j + 1 <= bc && check(ar, j + 1)) {
                s++;
            }
        }
        if (check(br, j)) {
            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;
        vector<pair<int,int>> st;
        if (check(ar, ac)) s++;
        if (check(ar, bc)) s++;
        if (check(br, ac)) s++;
        if (check(br, bc)) s++;
        return 1 + m - n - s;
    }
}

int solve(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() {
    vector<char> LOL{{'N', 'S', 'W', 'E'}};
    int MX = 3;
    while (1) {
        int r = rnd() % MX + 1, c = rnd() % MX + 1, m = rnd() % MX + 1, q = rnd() % MX + 1;
        char s[m];
        for (int i = 0; i < m; i++) {
            s[i] = LOL[rnd() % 4];
        }
        int x = rnd() % r, y = rnd() % c;
        int sr = x, sc = y;
        bool bad = 0;
        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++;
            }
            if (!(0 <= sr && sr < r && 0 <= sc && sc < c)) {
                bad = 1;
                break;
            }
        }
        if (bad) continue;
        init(r, c, x + 1, y + 1, m, s);
        for (int i = 0; i < q; i++) {
            int ar = rnd() % r, br = rnd() % r, ac = rnd() % c, bc = rnd() % c;
            if (ar > br) swap(ar, br);
            if (ac > bc) swap(ac, bc);
            auto res = solve(ar + 1, ac + 1, br + 1, bc + 1), res2 = colour(ar + 1, ac + 1, br + 1, bc + 1);
            if (res != res2) {
                cout << "BAD" << endl;
                cout << r << ' ' << c << ' ' << m << ' ' << endl;
                cout << x << ' ' << y << endl;
                for (int i = 0; i < m; i++) {
                    cout << s[i];
                }
                cout << endl;
                cout << ar << ' ' << ac << ' ' << br << ' ' << bc << endl;
                cout << res << ' ' << res2 << endl;
                return 0;
            }
        }
        cout << "OK" << endl;
    }
    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: 0 / 11
• Subtask 2: 0 / 12
• Subtask 3: 0 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26