oj.uz

Submission #945242

# Submission time Handle Problem Language Result Execution time Memory
945242 2024-03-13T14:51:11 Z TAhmed33 Land of the Rainbow Gold (APIO17_rainbow) C++
11 / 100
 483 ms 190292 KB 
#include <bits/stdc++.h>
#include "rainbow.h"
using namespace std;
const int MAXN = 2e6 + 25;
#define mid ((l + r) >> 1)
struct PersistentSegmentTree {
    set <pair <int, int>> points;
    const int L = 200000;
    int tree[MAXN], tl[MAXN], tr[MAXN], cnt;
    vector <pair <int, int>> roots;
    int new_node (int x, int y, int z) {
        ++cnt; tl[cnt] = x; tr[cnt] = y;
        tree[cnt] = z;
        return cnt;
    }
    int build (int l, int r) {
        if (l == r) {
            return ++cnt;
        }
        int left = build(l, mid), right = build(mid + 1, r);
        return new_node(left, right, 0);
    }
    int update (int l, int r, int a, int b, int node) {
        if (l == r) {
            int x = tree[node]; x += b;
            tree[++cnt] = x; return cnt;
        }
        if (a <= mid) {
            int z = update(l, mid, a, b, tl[node]);
            return new_node(z, tr[node], tree[z] + tree[tr[node]]);
        } else {
            int z = update(mid + 1, r, a, b, tr[node]);
            return new_node(tl[node], z, tree[z] + tree[tl[node]]);
        }
    }
    int get (int l, int r, int a, int b, int node) {
        if (l > b || r < a) return 0;
        if (l >= a && r <= b) return tree[node];
        return get(l, mid, a, b, tl[node]) + get(mid + 1, r, a, b, tr[node]);
    }
    void init () {
        cnt = 0;
        int root = build(0, L);
        int prev = -1;
        for (auto [x, y] : points) {
            int z = update(0, L, y, 1, root);
            if (x != prev) {
                roots.push_back({prev, root});
                root = z; prev = x;
            } else root = z;
        }    
        roots.push_back({prev, root});
    }
    int getroot (int x) {
        int l = 0, r = (int)roots.size() - 1, ans = -1;
        while (l <= r) {
            if (roots[mid].first <= x) {
                ans = mid; l = mid + 1;
            } else {
                r = mid - 1;
            }
        }  
        return ans == -1 ? -1 : roots[ans].second;
    }
    int query (int a, int b, int c, int d) {
        auto g = getroot(a - 1), h = getroot(c);
        int ret = 0;
        ret += get(0, L, b, d, h);
        ret -= get(0, L, b, d, g);
        return ret;
    }
} cur[4];
typedef long long ll;
int dx[4] = {0, -1, 0, 1}, dy[4] = {1, 0, -1, 0};
int mny, mxy, mnx, mxx;
map <char, int> lk = {
    {'E', 0},
    {'N', 1},
    {'W', 2},
    {'S', 3}
};
int n, m;
set <pair <int, int>> badcells, badvertedges, badhoredges, badfaces;
void insert (int x, int y) {
    if (badcells.count({x, y})) return;
    badcells.insert({x, y});
    if (y > 0 && !badhoredges.count({x, y - 1})) {
        badhoredges.insert({x, y - 1});
    }
    if (x > 0 && !badvertedges.count({x - 1, y})) {
        badvertedges.insert({x - 1, y});
    }
    if (y < m && !badhoredges.count({x, y})) {
        badhoredges.insert({x, y});
    }
    if (x < n && !badvertedges.count({x, y})) {
        badvertedges.insert({x, y});
    }
    if (y > 0 && x > 0 && !badfaces.count({x - 1, y - 1})) {
        badfaces.insert({x - 1, y - 1});
    }
    if (y > 0 && x + 1 < n && !badfaces.count({x, y - 1})) {
        badfaces.insert({x, y - 1});
    }
    if (y + 1 < m && x > 0 && !badfaces.count({x - 1, y})) {
        badfaces.insert({x - 1, y});
    }
    if (y + 1 < m && x + 1 < n && !badfaces.count({x, y})) {
        badfaces.insert({x, y});
    }
}
void init (int N, int M, int x, int y, int z, char *s) {
    n = N; m = M;
    x--; y--;
    mny = mxy = y; mnx = mxx = x;
    insert(x, y);
    for (int i = 0; i < z; i++) {
        x += dx[lk[s[i]]]; y += dy[lk[s[i]]];
        mny = min(mny, y);
        mxy = max(mxy, y);
        mnx = min(mnx, x);
        mxx = max(mxx, x);
        insert(x, y);
    }
    cur[0].points = badcells; cur[0].init();
    cur[1].points = badvertedges; cur[1].init();
    cur[2].points = badhoredges; cur[2].init();
    cur[3].points = badfaces; cur[3].init();
}
ll querycell (int a, int b, int c, int d) {
    return cur[0].query(a, b, c, d);
}
ll queryvert (int a, int b, int c, int d) {
    return cur[1].query(a, b, c, d);
}
ll queryhor (int a, int b, int c, int d) {
    return cur[2].query(a, b, c, d);
}
ll queryface (int a, int b, int c, int d) {
    return cur[3].query(a, b, c, d);
}
int colour (int ar, int ac, int br, int bc) {
    ar--; br--; ac--; bc--;
    if (ar > br) swap(ar, br);
    if (ac > bc) swap(ac, bc);
    ll v = 0, e = 0, f = 0;
    v = (br - ar + 1) * 1ll * (bc - ac + 1);
    v -= querycell(ar, ac, br, bc);
    ll e1 = (br - ar) * 1ll * (bc - ac + 1);
    if (ar < br) e1 -= queryvert(ar, ac, br - 1, bc);
    ll e2 = (br - ar + 1) * 1ll * (bc - ac);
    if (ac < bc) e2 -= queryhor(ar, ac, br, bc - 1);
    e = e1 + e2;
    f = (br - ar) * 1ll * (bc - ac);
    if (ar < br && ac < bc) f -= queryface(ar, ac, br - 1, bc - 1);
    if (ar < mnx && br > mxx && ac < mny && bc > mxy) f++;
    return v - e + f;
}

Compilation message

rainbow.cpp: In member function 'void PersistentSegmentTree::init()':
rainbow.cpp:45:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   45 |         for (auto [x, y] : points) {
      |                   ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 43608 KB Output is correct
2 Correct 13 ms 44176 KB Output is correct
3 Correct 9 ms 43612 KB Output is correct
4 Correct 9 ms 43868 KB Output is correct
5 Correct 12 ms 44220 KB Output is correct
6 Correct 8 ms 43612 KB Output is correct
7 Correct 7 ms 43700 KB Output is correct
8 Correct 7 ms 43692 KB Output is correct
9 Correct 7 ms 43704 KB Output is correct
10 Correct 7 ms 43608 KB Output is correct
11 Correct 10 ms 43864 KB Output is correct
12 Correct 11 ms 43868 KB Output is correct
13 Correct 12 ms 46428 KB Output is correct
14 Correct 15 ms 46548 KB Output is correct
15 Correct 7 ms 43608 KB Output is correct
16 Correct 7 ms 43612 KB Output is correct
17 Correct 7 ms 43668 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 43612 KB Output is correct
2 Correct 7 ms 43668 KB Output is correct
3 Incorrect 483 ms 121940 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

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

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 43608 KB Output is correct
2 Correct 13 ms 44176 KB Output is correct
3 Correct 9 ms 43612 KB Output is correct
4 Correct 9 ms 43868 KB Output is correct
5 Correct 12 ms 44220 KB Output is correct
6 Correct 8 ms 43612 KB Output is correct
7 Correct 7 ms 43700 KB Output is correct
8 Correct 7 ms 43692 KB Output is correct
9 Correct 7 ms 43704 KB Output is correct
10 Correct 7 ms 43608 KB Output is correct
11 Correct 10 ms 43864 KB Output is correct
12 Correct 11 ms 43868 KB Output is correct
13 Correct 12 ms 46428 KB Output is correct
14 Correct 15 ms 46548 KB Output is correct
15 Correct 7 ms 43608 KB Output is correct
16 Correct 7 ms 43612 KB Output is correct
17 Correct 7 ms 43668 KB Output is correct
18 Runtime error 190 ms 190292 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 43608 KB Output is correct
2 Correct 13 ms 44176 KB Output is correct
3 Correct 9 ms 43612 KB Output is correct
4 Correct 9 ms 43868 KB Output is correct
5 Correct 12 ms 44220 KB Output is correct
6 Correct 8 ms 43612 KB Output is correct
7 Correct 7 ms 43700 KB Output is correct
8 Correct 7 ms 43692 KB Output is correct
9 Correct 7 ms 43704 KB Output is correct
10 Correct 7 ms 43608 KB Output is correct
11 Correct 10 ms 43864 KB Output is correct
12 Correct 11 ms 43868 KB Output is correct
13 Correct 12 ms 46428 KB Output is correct
14 Correct 15 ms 46548 KB Output is correct
15 Correct 7 ms 43608 KB Output is correct
16 Correct 7 ms 43612 KB Output is correct
17 Correct 7 ms 43668 KB Output is correct
18 Runtime error 190 ms 190292 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -