oj.uz

Submission #945243

# Submission time Handle Problem Language Result Execution time Memory
945243 2024-03-13T14:52:42 Z TAhmed33 Land of the Rainbow Gold (APIO17_rainbow) C++
11 / 100
 237 ms 189980 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; assert(cnt < MAXN); tl[cnt] = x; tr[cnt] = y;
        tree[cnt] = z;
        return cnt;
    }
    int build (int l, int r) {
        if (l == r) {
            cnt++; assert(cnt < MAXN);
            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;
            cnt++; assert(cnt < MAXN);
            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:47:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |         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 11 ms 44136 KB Output is correct
3 Correct 10 ms 43612 KB Output is correct
4 Correct 9 ms 43612 KB Output is correct
5 Correct 11 ms 44228 KB Output is correct
6 Correct 7 ms 43612 KB Output is correct
7 Correct 7 ms 43612 KB Output is correct
8 Correct 7 ms 43612 KB Output is correct
9 Correct 8 ms 43696 KB Output is correct
10 Correct 8 ms 43612 KB Output is correct
11 Correct 10 ms 43864 KB Output is correct
12 Correct 11 ms 43868 KB Output is correct
13 Correct 13 ms 46428 KB Output is correct
14 Correct 13 ms 46428 KB Output is correct
15 Correct 8 ms 43612 KB Output is correct
16 Correct 8 ms 43660 KB Output is correct
17 Correct 8 ms 43608 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 43660 KB Output is correct
2 Correct 8 ms 43608 KB Output is correct
3 Runtime error 155 ms 141140 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 43612 KB Output is correct
2 Runtime error 237 ms 125992 KB Execution killed with signal 6
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 11 ms 44136 KB Output is correct
3 Correct 10 ms 43612 KB Output is correct
4 Correct 9 ms 43612 KB Output is correct
5 Correct 11 ms 44228 KB Output is correct
6 Correct 7 ms 43612 KB Output is correct
7 Correct 7 ms 43612 KB Output is correct
8 Correct 7 ms 43612 KB Output is correct
9 Correct 8 ms 43696 KB Output is correct
10 Correct 8 ms 43612 KB Output is correct
11 Correct 10 ms 43864 KB Output is correct
12 Correct 11 ms 43868 KB Output is correct
13 Correct 13 ms 46428 KB Output is correct
14 Correct 13 ms 46428 KB Output is correct
15 Correct 8 ms 43612 KB Output is correct
16 Correct 8 ms 43660 KB Output is correct
17 Correct 8 ms 43608 KB Output is correct
18 Runtime error 186 ms 189980 KB Execution killed with signal 6
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 11 ms 44136 KB Output is correct
3 Correct 10 ms 43612 KB Output is correct
4 Correct 9 ms 43612 KB Output is correct
5 Correct 11 ms 44228 KB Output is correct
6 Correct 7 ms 43612 KB Output is correct
7 Correct 7 ms 43612 KB Output is correct
8 Correct 7 ms 43612 KB Output is correct
9 Correct 8 ms 43696 KB Output is correct
10 Correct 8 ms 43612 KB Output is correct
11 Correct 10 ms 43864 KB Output is correct
12 Correct 11 ms 43868 KB Output is correct
13 Correct 13 ms 46428 KB Output is correct
14 Correct 13 ms 46428 KB Output is correct
15 Correct 8 ms 43612 KB Output is correct
16 Correct 8 ms 43660 KB Output is correct
17 Correct 8 ms 43608 KB Output is correct
18 Runtime error 186 ms 189980 KB Execution killed with signal 6
19 Halted 0 ms 0 KB -