Submission #569484

#	Time	Username	Problem	Language	Result	Execution time	Memory
569484		saarang123	Land of the Rainbow Gold (APIO17_rainbow)	C++17	0 / 100	1 ms	596 KiB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;


const int MXN = 200 * 1000 + 3;
const vector<array<int, 2>> dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
bool f[2][MXN], is[MXN];
int cnt[MXN];
int n, m;

int con(int i, int j) {
    return m * i + j;
}

void init(int R, int C, int sr, int sc, int M, char *S) {
    n = R, m = C;
    int x = sr - 1, y = sc - 1;
    f[x][y] = true;
    for(int i = 0; i < M; i++) {
        char c = S[i];
        if(c == 'N')
            x--;
        else if(c == 'S')
            x++;
        else if(c == 'W')
            y--;
        else
            y++;
        f[x][y] = true;
    }
    bool last = true;
    for(int i = 0; i < m; i++) {
        if(i)
            cnt[i] += cnt[i - 1];
        if(f[0][i] && f[1][i]) {
            is[i] = true;
            last = true; continue;
        }
        if(last)
            cnt[i]++, last = 0;
    }
}

int colour(int ar, int ac, int br, int bc) {
    ar--, ac--, br--, bc--;
    if(ac == bc && ar == br)
        return !f[ar][ac];
    else if(ac == bc && ar != br)
        return max(!f[0][ac], !f[1][ac]);
    else {
        int ans = cnt[bc] - (ac ? cnt[ac - 1] : 0);
        if(ac && !is[ac])
            ans += !is[ac - 1];
        return ans;
    }
}

#ifdef saarang
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

• Subtask 1: 0 / 11
• Subtask 2: 0 / 12
• Subtask 3: 0 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26