oj.uz

Submission #1054251

# Submission time Handle Problem Language Result Execution time Memory
1054251 2024-08-12T08:02:15 Z 정민찬(#11058) Land of the Rainbow Gold (APIO17_rainbow) C++14
12 / 100
 71 ms 28112 KB 
#include "rainbow.h"
#include <bits/stdc++.h>

using namespace std;

int board[3][200010];

struct Node{
    int l, r, val;
    int typ;
};

Node Merge(Node u, Node v) {
    Node ret;
    ret.l = u.l; ret.r = v.r;
    ret.typ = u.typ;
    if (ret.typ == 3) {
        if (board[1][u.r] && board[2][u.r]) ret.val = u.val + v.val;
        else if (board[1][v.l] && board[2][v.l]) ret.val = u.val + v.val;
        else ret.val = u.val + v.val - 1;
    }
    else if (ret.typ == 1) {
        if (board[1][u.r] || board[1][v.l]) ret.val = u.val + v.val;
        else ret.val = u.val + v.val - 1;
    }
    else if (ret.typ == 2) {
        if (board[2][u.r] || board[2][v.l]) ret.val = u.val + v.val;
        else ret.val = u.val + v.val - 1;
    }
    
    return ret;
}

struct SegmentTree{
    vector<Node> tree;
    void init(int n) {
        int sz = 1 << __lg(n-1) + 2;
        tree.assign(sz, {0,0,0});
    }
    void build(int node, int s, int e, int typ) {
        if (s == e) {
            tree[node].l = tree[node].r = s;
            tree[node].typ = typ;
            if (typ == 1) {
                tree[node].val = board[1][s] == 0;
            }
            else if (typ == 2) {
                tree[node].val = board[2][s] == 0;
            }
            else {
                tree[node].val = board[1][s] == 0 || board[2][s] == 0;
            }
            return;
        }
        int mid = s + e >> 1;
        build(node*2, s, mid, typ);
        build(node*2+1, mid+1, e, typ);
        tree[node] = Merge(tree[node*2], tree[node*2+1]);
    }
    Node query(int node, int s, int e, int l, int r) {
        if (l <= s && e <= r) return tree[node];
        int mid = s + e >> 1;
        if (r <= mid) return query(node*2, s, mid, l, r);
        if (l >= mid+1) return query(node*2+1, mid+1, e, l, r);
        return Merge(query(node*2, s, mid, l, r), query(node*2+1, mid+1, e, l, r));
    }
};

SegmentTree seg1, seg2, seg3;
int c;

void init(int R, int C, int sr, int sc, int M, char *S) {
    c = C;
    int x = sr, y = sc;
    board[x][y] = 1;
    for (int i=0; i<M; i++) {
        if (S[i] == 'N') x --;
        if (S[i] == 'S') x ++;
        if (S[i] == 'W') y --;
        if (S[i] == 'E') y ++;
        board[x][y] = 1;
    }
    seg1.init(C);
    seg2.init(C);
    seg3.init(C);
    seg1.build(1, 1, C, 1);
    seg2.build(1, 1, C, 2);
    seg3.build(1, 1, C, 3);
}

int colour(int ar, int ac, int br, int bc) {
    if (ar == 1 && br == 1) return seg1.query(1, 1, c, ac, bc).val;
    if (ar == 2 && br == 2) return seg2.query(1, 1, c, ac, bc).val;
    return seg3.query(1, 1, c, ac, bc).val;
}
/*
static int R, C, M, Q;
static int sr, sc;
static char S[100000 + 5];

int main() {
    scanf("%d %d %d %d", &R, &C, &M, &Q);
    scanf("%d %d", &sr, &sc);
    if (M > 0) {
        scanf(" %s ", S);
    }

    init(R, C, sr, sc, M, S);

    int query;
    for (query = 0; query < Q; query++) {
        int ar, ac, br, bc;
        scanf("%d %d %d %d", &ar, &ac, &br, &bc);
        printf("%d\n", colour(ar, ac, br, bc));
    }

    return 0;
}*/

Compilation message

rainbow.cpp: In member function 'void SegmentTree::init(int)':
rainbow.cpp:37:33: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   37 |         int sz = 1 << __lg(n-1) + 2;
      |                       ~~~~~~~~~~^~~
rainbow.cpp: In member function 'void SegmentTree::build(int, int, int, int)':
rainbow.cpp:55:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |         int mid = s + e >> 1;
      |                   ~~^~~
rainbow.cpp: In member function 'Node SegmentTree::query(int, int, int, int, int)':
rainbow.cpp:62:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |         int mid = s + e >> 1;
      |                   ~~^~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 348 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 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 59 ms 27788 KB Output is correct
4 Correct 71 ms 27676 KB Output is correct
5 Correct 64 ms 27728 KB Output is correct
6 Correct 65 ms 27752 KB Output is correct
7 Correct 67 ms 27732 KB Output is correct
8 Correct 59 ms 27736 KB Output is correct
9 Correct 68 ms 28112 KB Output is correct
10 Correct 65 ms 27732 KB Output is correct
11 Correct 61 ms 27816 KB Output is correct
12 Correct 32 ms 27772 KB Output is correct
13 Correct 31 ms 27740 KB Output is correct
14 Correct 31 ms 27824 KB Output is correct
15 Correct 33 ms 27728 KB Output is correct
16 Correct 64 ms 27856 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Runtime error 1 ms 604 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 0 ms 348 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 0 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -