oj.uz

Submission #172661

# Submission time Handle Problem Language Result Execution time Memory
172661 2020-01-02T09:55:36 Z dolphingarlic Land of the Rainbow Gold (APIO17_rainbow) C++14
11 / 100
 408 ms 182796 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
using namespace std;

int cnt = 1, segtree[2020202], left_c[2020202], right_c[2020202];

struct Segtree {
    set<int> data[200001];
    int roots[200002];

    void add(int x, int y) { data[x].insert(y); }

    void build() {
        FOR(i, 1, 200001) {
            roots[i + 1] = roots[i];
            for (int j : data[i]) update(j, roots[i + 1]);
        }
    }

    void update(int pos, int &node, int l = 1, int r = 200000) {
        segtree[cnt] = segtree[node] + 1;
        left_c[cnt] = left_c[node];
        right_c[cnt] = right_c[node];
        node = cnt++;

        if (l == r) return;
        int mid = (l + r) / 2;
        if (pos > mid) update(pos, right_c[node], mid + 1, r);
        else update(pos, left_c[node], l, mid);
    }

    int query(int l1, int r1, int l2, int r2) {
        if (l2 > r2) return 0;
        return query(l2, r2, roots[r1 + 1], 1, 200000) - query(l2, r2, roots[l1], 1, 200000);
    }
    int query(int a, int b, int node, int l, int r) {
        if (a > r || b < l) return 0;
        if (a <= l && b >= r) return segtree[node];
        int mid = (l + r) / 2;
        return query(a, b, left_c[node], l, mid) + query(a, b, right_c[node], mid + 1, r);
    }
} vertices, edges_horiz, edges_vert, rivers;

int mx_r, mn_r, mx_c, mn_c;
 
void add_river(int x, int y) {
    vertices.add(x, y);
    vertices.add(x + 1, y);
    vertices.add(x, y + 1);
    vertices.add(x + 1, y + 1);
    edges_horiz.add(x, y);
    edges_horiz.add(x + 1, y);
    edges_vert.add(x, y);
    edges_vert.add(x, y + 1);
    rivers.add(x, y);
}
 
void init(int R, int C, int sr, int sc, int M, char *S) {
    add_river(sr, sc);
    mx_r = mn_r = sr;
    mx_c = mn_c = sc;
    FOR(i, 0, M) {
        if (S[i] == 'N') sr--;
        if (S[i] == 'E') sc++;
        if (S[i] == 'S') sr++;
        if (S[i] == 'W') sc--;
        add_river(sr, sc);
        mx_r = max(mx_r, sr);
        mn_r = min(mn_r, sr);
        mx_c = max(mx_c, sc);
        mn_c = min(mn_c, sc);
    }
    vertices.build();
    edges_horiz.build();
    edges_vert.build();
    rivers.build();
}
 
int colour(int ar, int ac, int br, int bc) {
    int E = edges_horiz.query(ar + 1, br, ac, bc) + edges_vert.query(ar, br, ac + 1, bc);
    int V = vertices.query(ar + 1, br, ac + 1, bc);
    int R = rivers.query(ar, br, ac, bc);
    int C = (ar >= mn_r || br <= mx_r || ac >= mn_c || bc <= mx_c ? 1 : 2);
    return E - V + C - R;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 41336 KB Output is correct
2 Correct 50 ms 42360 KB Output is correct
3 Correct 47 ms 41336 KB Output is correct
4 Correct 47 ms 41464 KB Output is correct
5 Correct 50 ms 42616 KB Output is correct
6 Correct 44 ms 41080 KB Output is correct
7 Correct 44 ms 41080 KB Output is correct
8 Correct 44 ms 41080 KB Output is correct
9 Correct 44 ms 41104 KB Output is correct
10 Correct 44 ms 41008 KB Output is correct
11 Correct 47 ms 41524 KB Output is correct
12 Correct 48 ms 42104 KB Output is correct
13 Correct 51 ms 43128 KB Output is correct
14 Correct 52 ms 43768 KB Output is correct
15 Correct 44 ms 41080 KB Output is correct
16 Correct 44 ms 41084 KB Output is correct
17 Correct 44 ms 41080 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 41084 KB Output is correct
2 Correct 44 ms 41080 KB Output is correct
3 Runtime error 279 ms 159068 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 41080 KB Output is correct
2 Runtime error 408 ms 182796 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 41336 KB Output is correct
2 Correct 50 ms 42360 KB Output is correct
3 Correct 47 ms 41336 KB Output is correct
4 Correct 47 ms 41464 KB Output is correct
5 Correct 50 ms 42616 KB Output is correct
6 Correct 44 ms 41080 KB Output is correct
7 Correct 44 ms 41080 KB Output is correct
8 Correct 44 ms 41080 KB Output is correct
9 Correct 44 ms 41104 KB Output is correct
10 Correct 44 ms 41008 KB Output is correct
11 Correct 47 ms 41524 KB Output is correct
12 Correct 48 ms 42104 KB Output is correct
13 Correct 51 ms 43128 KB Output is correct
14 Correct 52 ms 43768 KB Output is correct
15 Correct 44 ms 41080 KB Output is correct
16 Correct 44 ms 41084 KB Output is correct
17 Correct 44 ms 41080 KB Output is correct
18 Runtime error 237 ms 155584 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 41336 KB Output is correct
2 Correct 50 ms 42360 KB Output is correct
3 Correct 47 ms 41336 KB Output is correct
4 Correct 47 ms 41464 KB Output is correct
5 Correct 50 ms 42616 KB Output is correct
6 Correct 44 ms 41080 KB Output is correct
7 Correct 44 ms 41080 KB Output is correct
8 Correct 44 ms 41080 KB Output is correct
9 Correct 44 ms 41104 KB Output is correct
10 Correct 44 ms 41008 KB Output is correct
11 Correct 47 ms 41524 KB Output is correct
12 Correct 48 ms 42104 KB Output is correct
13 Correct 51 ms 43128 KB Output is correct
14 Correct 52 ms 43768 KB Output is correct
15 Correct 44 ms 41080 KB Output is correct
16 Correct 44 ms 41084 KB Output is correct
17 Correct 44 ms 41080 KB Output is correct
18 Runtime error 237 ms 155584 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Halted 0 ms 0 KB -