oj.uz

Submission #567467

# Submission time Handle Problem Language Result Execution time Memory
567467 2022-05-23T14:35:42 Z ngpin04 Land of the Rainbow Gold (APIO17_rainbow) C++14
12 / 100
 461 ms 84184 KB 
#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;

set <pair <int, int>> s;

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

    s.insert({sr, sc});
    for (int i = 0; i < M; i++) {
        int dir = fix(S[i]);
        sr += dx[dir];
        sc += dy[dir];
        s.insert({sr, sc});
        // cerr << sr << " " << sc << "\n";
    }

    for (const auto &[x, y] : s) {
        int a = false, b = false;
        if (s.find({x + 1, y}) != s.end()) {
            col.fakeupdate(x + 1, y);
            a = true;
        }
        
        if (s.find({x, y + 1}) != s.end()) {
            row.fakeupdate(x, y + 1);
            b = true;
        }

        if (a && b) {
            if (s.find({x + 1, y + 1}) != s.end()) 
                face.fakeupdate(x + 1, y + 1);
        }

        cell.fakeupdate(x, y);
    }

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

    for (const auto &[x, y] : s) {
        int a = false, b = false;
        if (s.find({x + 1, y}) != s.end()) {
            col.update(x + 1, y);
            a = true;
        }
        
        if (s.find({x, y + 1}) != s.end()) {
            row.update(x, y + 1);
            b = true;
        }

        if (a && b) {
            if (s.find({x + 1, y + 1}) != s.end()) 
                face.update(x + 1, y + 1);
        }

        cell.update(x, y);
    }
}

int colour(int x, int y, int u, int v) {
    int res = 0;
    int V = cell.getsum(x, y, u, v);
    int E = col.getsum(x + 1, y, u, v) + row.getsum(x, y + 1, u, v);
    E += cell.getsum(x, y, x, v);
    E += cell.getsum(x, y, u, y);
    E += cell.getsum(u, y, u, v);
    E += cell.getsum(x, v, u, v);
    int F = 0;
    F += face.getsum(x + 1, y + 1, u, v);
    F += row.getsum(x, y + 1, x, v);
    F += row.getsum(u, y + 1, u, v);
    F += col.getsum(x + 1, y, u, y);
    F += col.getsum(x + 1, v, u, v);
    F += s.count({x, y}) + s.count({x, v}) + s.count({u, y}) + s.count({u, v});
    // cerr << V << " " << E << "\n";
    return 1 + (E - V - F);
}

//#include "grader.cpp"

Compilation message

rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:105:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  105 |     for (const auto &[x, y] : s) {
      |                      ^
rainbow.cpp:130:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  130 |     for (const auto &[x, y] : s) {
      |                      ^
rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:152:9: warning: unused variable 'res' [-Wunused-variable]
  152 |     int res = 0;
      |         ^~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 295 ms 8020 KB Output is correct
4 Correct 461 ms 10996 KB Output is correct
5 Correct 429 ms 10972 KB Output is correct
6 Correct 363 ms 9944 KB Output is correct
7 Correct 407 ms 9460 KB Output is correct
8 Correct 81 ms 3884 KB Output is correct
9 Correct 403 ms 10992 KB Output is correct
10 Correct 432 ms 10876 KB Output is correct
11 Correct 362 ms 9892 KB Output is correct
12 Correct 192 ms 10212 KB Output is correct
13 Correct 188 ms 10960 KB Output is correct
14 Correct 206 ms 10824 KB Output is correct
15 Correct 185 ms 9896 KB Output is correct
16 Correct 318 ms 9204 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 277 ms 80400 KB Output is correct
3 Correct 206 ms 79768 KB Output is correct
4 Correct 353 ms 84184 KB Output is correct
5 Correct 195 ms 76392 KB Output is correct
6 Correct 167 ms 68768 KB Output is correct
7 Incorrect 242 ms 72376 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -