Submission #567501

#	Time	Username	Problem	Language	Result	Execution time	Memory
567501		ngpin04	Land of the Rainbow Gold (APIO17_rainbow)	C++14	0 / 100	1034 ms	137844 KiB

rainbow

#include <bits/stdc++.h>
#include "rainbow.h"
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
    if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
    if (a < b) {a = b; return true;} return false;
}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) {
    return l + rd() % (r - l + 1);
}
const int N = 1e5 + 5; 
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

struct BIT2D {
    int n;
    vector <vector <int>> val;
    vector <vector <int>> bit;

    BIT2D(int _n = 0) {
        n = _n;
        bit.resize(n + 5);
        val.resize(n + 5);
    }

    void fakeupdate(int x, int y) {
        for (; x <= n; x += x & -x) 
            val[x].push_back(y);
    }

    void build() {
        for (int i = 1; i <= n; i++) {
            sort(ALL(val[i]));
            val[i].resize(unique(ALL(val[i])) - val[i].begin());
            bit[i].resize(val[i].size() + 1);
        }
    }

    void update(int x, int y) {
        for (; x <= n; x += x & -x) {
            int i = lower_bound(ALL(val[x]), y) - val[x].begin() + 1;
            for (; i < (int) bit[x].size(); i += i & -i)
                bit[x][i]++;
        }
    }

    int getsum(int x, int y) {
        int res = 0;
        for (; x; x -= x & -x) {
            int i = upper_bound(ALL(val[x]), y) - val[x].begin();
            for (; i; i -= i & -i)
                res += bit[x][i];
        }
        return res;
    }

    int getsum(int x, int y, int u, int v) {
        if (x > u || y > v)
            return 0;
        return (getsum(u, v) + getsum(x - 1, y - 1)) 
        -      (getsum(u, y - 1) + getsum(x - 1, v));
    }
};

int fix(char c) {
    if (c == 'W') 
        return 3;
    if (c == 'N') 
        return 2;
    if (c == 'E')
        return 1;
    return 0;
}

BIT2D row, col, cell, face;

int maxx, maxy, minx, miny;

void init(int R, int C, int sr, int sc, int M, char *S) {
    row = col = cell = face = BIT2D(R + 1);

    set <pair <int, int>> s, r, c, f;

    minx = maxx = sr;
    miny = maxy = sc;
    f.insert({sr + 1, sc + 1});
    s.insert({sr, sc});
    s.insert({sr + 1, sc});
    s.insert({sc, sr + 1});
    s.insert({sc + 1, sr + 1});
    for (int i = 0; i < M; i++) {
        int dir = fix(S[i]);
        sr += dx[dir];
        sc += dy[dir];

        s.insert({sr, sc});
        s.insert({sr + 1, sc});
        s.insert({sr, sc + 1});
        s.insert({sr + 1, sc + 1});

        f.insert({sr + 1, sc + 1});
        
        r.insert({sr, sc + 1});
        r.insert({sr + 1, sc + 1});

        c.insert({sr + 1, sc});
        c.insert({sr + 1, sc + 1});

        maxi(maxx, sr);
        maxi(maxy, sc);
        mini(minx, sr);
        mini(miny, sc);
    }

    for (auto [x, y] : s) 
        cell.fakeupdate(x, y);

    for (auto [x, y] : r)
        row.fakeupdate(x, y);

    for (auto [x, y] : c)
        col.fakeupdate(x, y);

    for (auto [x, y] : f)
        face.fakeupdate(x, y);


    cell.build();
    row.build();
    col.build();
    face.build();

    for (auto [x, y] : s) 
        cell.update(x, y);

    for (auto [x, y] : r)
        row.update(x, y);

    for (auto [x, y] : c)
        col.update(x, y);

    for (auto [x, y] : f)
        face.update(x, y);
}

int colour(int x, int y, int u, int v) {
    int res = 0;
    int C = 1 + (x < minx && maxx < u && y < miny && maxy < v);
    v++;
    u++;
    int R = face.getsum(x + 1, y + 1, u, v);
    int V = cell.getsum(x + 1, y + 1, u - 1, v - 1);
    int E = row.getsum(x + 1, y + 1, u - 1, v) 
        +   col.getsum(x + 1, y + 1, u, v - 1);

    // cerr << V << " " << E << " " << C << " " << R << "\n";
    int F = 1 + (C + E - V);
    return F - R - 1;    
}

//#include "grader.cpp"

Compilation message (stderr)

rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:129:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  129 |     for (auto [x, y] : s)
      |               ^
rainbow.cpp:132:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  132 |     for (auto [x, y] : r)
      |               ^
rainbow.cpp:135:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  135 |     for (auto [x, y] : c)
      |               ^
rainbow.cpp:138:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  138 |     for (auto [x, y] : f)
      |               ^
rainbow.cpp:147:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  147 |     for (auto [x, y] : s)
      |               ^
rainbow.cpp:150:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  150 |     for (auto [x, y] : r)
      |               ^
rainbow.cpp:153:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  153 |     for (auto [x, y] : c)
      |               ^
rainbow.cpp:156:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  156 |     for (auto [x, y] : f)
      |               ^
rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:161:9: warning: unused variable 'res' [-Wunused-variable]
  161 |     int res = 0;
      |         ^~~

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