Submission #569395

#	Time	Username	Problem	Language	Result	Execution time	Memory
569395		Ooops_sorry	Land of the Rainbow Gold (APIO17_rainbow)	C++14	0 / 100	3063 ms	5052 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;

void init(int R, int C, int sr, int sc, int m, char *s) {
    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++;
        }
        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 (ac != bc && 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 (check(ar, j + 1)) {
                s++;
            }
        }
        if (ar != br && check(br, j)) {
            if (j > ac) cnt++;
            if (check(br, j + 1)) {
                s++;
            }
        }
    }
    if (cnt == 0) {
        if (n == 0) {
            return 1;
        } else {
            return 2 + m - n;
        }
    } else {
        m += cnt;
        set<pair<int,int>> st;
        st.insert({ar, ac});
        st.insert({ar, bc});
        st.insert({br, ac});
        st.insert({br, bc});
        for (auto to : st) {
            if (check(to.first, to.second)) {
                m++;
                s++;
            }
        }
        return 1 + m - n - s;
    }
}


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