Submission #408621

#	Time	Username	Problem	Language	Result	Execution time	Memory
408621		abc864197532	Land of the Rainbow Gold (APIO17_rainbow)	C++17	12 / 100	71 ms	4552 KiB

rainbow

#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair <int, int>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define info() cerr << __PRETTY_FUNCTION__ << ": " << __LINE__ << endl
void abc() {cerr << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cerr << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.X >> a.Y;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.X << ", " << a.Y << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}
template <typename T> struct vv : vector <vector <T>> {
    vv(int n, int m, T v) : vector <vector <T>> (n, vector <T>(m, v)) {}
    vv() {}
};
template <typename T> struct vvv : vector <vv <T>> {
    vvv(int n, int m, int k, T v) : vector <vv <T>> (n, vv <T>(m, k, v)) {}
    vvv() {}
};
#ifdef Doludu
#define test(args...) info(), abc("[" + string(#args) + "]", args)
#define owo
#include "rainbow-grader.cpp"
#else
#define test(args...)
#define owo ios::sync_with_stdio(false); cin.tie(0)
#endif
// const int mod = 998244353, N = 1000001, logN = 20, K = 111;

vv <bool> area;
int n, m;
vector <int> ans[3][2];

void init(int _n, int _m, int r, int c, int k, char *s) {
    r--, c--;
    n = _n, m = _m;
    area = vv <bool>(n, m, false);
    area[r][c] = true;
    for (int i = 0; i < k; ++i) {
        if (s[i] == 'W') c--;
        if (s[i] == 'E') c++;
        if (s[i] == 'N') r--;
        if (s[i] == 'S') r++;
        area[r][c] = true;
    }
    {
        for (int j = 0, k = 0; j < m; j = k) {
            for (; !area[0][k]; ++k);
            if (!area[0][j]) ans[0][0].pb(j), ans[0][1].pb(k);
            else k++;
        }
    }
    {
        for (int j = 0, k = 0; j < m; j = k) {
            for (; !area[1][k]; ++k);
            if (!area[1][j]) ans[1][0].pb(j), ans[1][1].pb(k);
            else k++;
        }
    }
    {
        for (int j = 0, k = 0; j < m; j = k) {
            for (; !area[0][k] || !area[1][k]; ++k);
            if (!area[0][j] || !area[1][j]) ans[2][0].pb(j), ans[2][1].pb(k);
            else k++;
        }
    }
}

int colour(int l1, int r1, int l2, int r2) {
    l1--, r1--;
    int x = 0;
    if (l1 == 0 && l2 == 2) {
        x = 2;
    } else if (l1 == 1 && l2 == 2) {
        x = 1;
    }
    int l = upper_bound(all(ans[x][1]), r1) - ans[x][1].begin();
    int r = lower_bound(all(ans[x][0]), r2) - ans[x][0].begin();
    test(l, r);
    return r - l;
    // 5 3
    // 8 6
    // 12 10
    // XXXOOXOOXXOO
}

/*
6 4 9 4
3 3
NWESSWEWS
2 3 2 3
3 2 4 4
5 3 6 4
1 2 5 3

2 5 6 2
1 1
SENEEE
1 2 1 4
1 1 2 4
 */

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