oj.uz

Submission #853906

# Submission time Handle Problem Language Result Execution time Memory
853906 2023-09-25T12:54:58 Z vuavisao Land of the Rainbow Gold (APIO17_rainbow) C++17
12 / 100
 157 ms 26288 KB 
#ifndef LOCAL
    #include "rainbow.h"
#endif
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define ll long long
using namespace std;
 
const int N = 1e5 + 10;
const int dx[] = {- 1, 0, 0, 1};
const int dy[] = {0, - 1, 1, 0};
 
struct SegTree {
    struct Node {
        int prf[2] = {0, 0}, suf[2] = {0, 0};
        int up = 0, down = 0, s = 0;
        Node() {};
        Node operator + (const Node& other) const {
            Node res;
            for(int i = 0; i < 2; ++ i) {
                res.prf[i] = this -> prf[i];
                res.suf[i] = other.suf[i];
            }
            res.up = this -> up + other.up;
            res.down = this -> down + other.down;
            res.s = this -> s + other.s;
            int have[2] = {(this -> suf[0] & other.prf[0]), (this -> suf[1] & other.prf[1])};
            res.up -= have[0];
            res.down -= have[1];
            res.s -= have[0] | have[1];
            return res;
        }
    };
 
    int n_node = 0;
    vector<Node> tree = {};
 
    void resize(int _n) { n_node = _n; tree.resize((n_node << 2) + 10); };
    SegTree() {};
    SegTree(int _n) { this -> resize(_n); };
 
    void update(int node, int l, int r, int idx, int val[2]) {
        if(l == r) {
            for(int i = 0; i < 2; ++ i) {
                tree[node].prf[i] = tree[node].suf[i] = val[i];
            }
            tree[node].up += val[0];
            tree[node].down += val[1];
            tree[node].s += val[0] | val[1];
            return;
        }
        int mid = (l + r) >> 1;
        if(idx <= mid) update(node << 1, l, mid, idx, val);
        else update(node << 1 | 1, mid + 1, r, idx, val);
        tree[node] = tree[node << 1] + tree[node << 1 | 1];
    }
 
    void Update(int idx, int val[2]) {
        return update(1, 1, n_node, idx, val);
    }
 
    Node query(int node, int l, int r, int L, int R) {
        // if(l > r || L > R || l > R || L > r) return Node();
        if(L <= l && r <= R) return tree[node]; 
        int mid = (l + r) >> 1;
        if(R <= mid) return query(node << 1, l, mid, L, R);
        else if(L > mid) return query(node << 1 | 1, mid + 1, r, L, R);
        return query(node << 1, l, mid, L, R) + query(node << 1 | 1, mid + 1, r, L, R);
    }
 
    Node Query(int l, int r) {
        return query(1, 1, n_node, l, r);
    }
};
 
int n, m, q;
int len, x, y;
char s[N];
 
bool un_go[3][200010];
SegTree st;
 
void init(int R, int C, int sr, int sc, int M, char *S) {
    n = R; m = C; x = sr; y = sc; len = M;
    for(int i = 0; i < len; ++ i) s[i] = S[i];
 
    un_go[x][y] = true;
    for(int i = 0; i < len; ++ i) {
        if(s[i] == 'N') -- x;
        else if(s[i] == 'S') ++ x;
        else if(s[i] == 'E') ++ y;
        else -- y;
        un_go[x][y] = true;
    }
 
    st.resize(m);
    for(int i = 1; i <= m; ++ i) {
        int val[2] = {!un_go[1][i], !un_go[2][i]};
        st.Update(i, val);
    }
}
 
int colour(int ar, int ac, int br, int bc) {
    int up = ar, le = ac, down = br, ri = bc;
    const auto& res = st.Query(le, ri);
    if(up == down) {
        if(up == 1) return res.up;
        else return res.down;
    } 
    else return res.s;
}
 
/// Code by vuavisao

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 105 ms 24656 KB Output is correct
4 Correct 139 ms 26288 KB Output is correct
5 Correct 105 ms 26144 KB Output is correct
6 Correct 112 ms 26220 KB Output is correct
7 Correct 100 ms 26284 KB Output is correct
8 Correct 136 ms 25984 KB Output is correct
9 Correct 120 ms 26272 KB Output is correct
10 Correct 103 ms 26288 KB Output is correct
11 Correct 99 ms 26196 KB Output is correct
12 Correct 66 ms 26192 KB Output is correct
13 Correct 64 ms 26144 KB Output is correct
14 Correct 65 ms 26128 KB Output is correct
15 Correct 66 ms 25940 KB Output is correct
16 Correct 157 ms 25936 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Runtime error 1 ms 856 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -