Submission #409510

#	Time	Username	Problem	Language	Result	Execution time	Memory
409510		abc864197532	Land of the Rainbow Gold (APIO17_rainbow)	C++17	100 / 100	1193 ms	442472 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, int v = 0) : vector <vector <T>> (n, vector <T>(m, v)) {}
    vv() {}
};
template <typename T> struct vvv : vector <vv <T>> {
    vvv(int n, int m, int k, int v = 0) : 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 = 200001, logN = 20, K = 111, NN = 4e7;

struct Seg {
    static Seg mem[NN], *pt;
    int l, r, m, sum;
    Seg* ch[2];
    Seg () = default;
    Seg (int _l, int _r) : l(_l), r(_r), m(l + r >> 1) {
        if (r - l > 1) {
            ch[0] = new (pt++) Seg(l, m);
            ch[1] = new (pt++) Seg(m, r);
        } else {
            sum = 0;
        }
    }
    Seg* modify(int p) {
        Seg *now = new (pt++) Seg(*this);
        now->sum++;
        if (r - l == 1) return now;
        else now->ch[p >= m] = now->ch[p >= m]->modify(p);
        return now;
    }
    int query(int a, int b) {
        if (a >= b) return 0;
        if (a <= l && r <= b) return sum;
        int ans = 0;
        if (a < m) ans += ch[0]->query(a, b);
        if (m < b) ans += ch[1]->query(a, b);
        return ans;
    }
} Seg::mem[NN], *Seg::pt = mem;

vector <Seg*> vertex, seg_row, seg_col, cell;
int mn_r = N, mx_r = 0, mn_c = N, mx_c = 0;

void init(int n, int m, int r, int c, int k, char *s) {
    r--, c--;
    vertex.pb(new (Seg::pt++) Seg(0, m + 1));
    seg_row.pb(new (Seg::pt++) Seg(0, m));
    seg_col.pb(new (Seg::pt++) Seg(0, m + 1));
    cell.pb(new Seg(0, m));
    vector <int> v[n + 1], sr[n + 1], sc[n], cc[n];
    auto add = [&](int r, int c) {
        v[r].pb(c);
        v[r].pb(c + 1);
        v[r + 1].pb(c);
        v[r + 1].pb(c + 1);
        sr[r].pb(c);
        sr[r + 1].pb(c);
        sc[r].pb(c);
        sc[r].pb(c + 1);
        cc[r].pb(c);
        mn_r = min(mn_r, r);
        mx_r = max(mx_r, r);
        mn_c = min(mn_c, c);
        mx_c = max(mx_c, c);
    };
    add(r, c);
    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++;
        add(r, c);
    }
    {
        for (int i = 0; i < n + 1; ++i) {
            sort(all(v[i]));
            v[i].resize(unique(all(v[i])) - v[i].begin());
            Seg* now = vertex.back();
            for (int j : v[i]) {
                now = now->modify(j);
            }
            vertex.pb(now);
        }
    }
    {
        for (int i = 0; i < n + 1; ++i) {
            sort(all(sr[i]));
            sr[i].resize(unique(all(sr[i])) - sr[i].begin());
            Seg* now = seg_row.back();
            for (int j : sr[i]) {
                now = now->modify(j);
            }
            seg_row.pb(now);
        }
    }
    {
        for (int i = 0; i < n; ++i) {
            sort(all(sc[i]));
            sc[i].resize(unique(all(sc[i])) - sc[i].begin());
            Seg* now = seg_col.back();
            for (int j : sc[i]) {
                now = now->modify(j);
            }
            seg_col.pb(now);
        }
    }
    {
        for (int i = 0; i < n; ++i) {
            sort(all(cc[i]));
            cc[i].resize(unique(all(cc[i])) - cc[i].begin());
            Seg* now = cell.back();
            for (int j : cc[i]) {
                now = now->modify(j);
            }
            cell.pb(now);
        }
    }
}

int colour(int l1, int r1, int l2, int r2) {
    l1--, r1--;
    // F = E - V + 1 + C
    // ans = E - V + C - A, A -> cell
    int V = vertex[l2]->query(r1 + 1, r2) - vertex[l1 + 1]->query(r1 + 1, r2) + (l2 - l1 + 1) * 2 + (r2 - r1 + 1) * 2 - 4;
    int E1 = seg_row[l2]->query(r1, r2) - seg_row[l1 + 1]->query(r1, r2) + (r2 - r1) * 2;
    int E2 = seg_col[l2]->query(r1 + 1, r2) - seg_col[l1]->query(r1 + 1, r2) + (l2 - l1) * 2;
    int C = (l1 < mn_r && mx_r + 1 < l2 && r1 < mn_c && mx_c +1 < r2 ? 2 : 1);
    int A = cell[l2]->query(r1, r2) - cell[l1]->query(r1, r2);
    return E1 + E2 - V + C - A;
}

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

Compilation message (stderr)

rainbow.cpp: In constructor 'Seg::Seg(int, int)':
rainbow.cpp:54:46: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |     Seg (int _l, int _r) : l(_l), r(_r), m(l + r >> 1) {
      |                                            ~~^~~

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