oj.uz

Submission #843279

# Submission time Handle Problem Language Result Execution time Memory
843279 2023-09-03T21:22:08 Z Tob Land of the Rainbow Gold (APIO17_rainbow) C++14
100 / 100
 294 ms 271760 KB 
#include "rainbow.h"
#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

const int N = 4e5 + 7;

int n, m, cnt, mnx, mxx, mny, mxy;
int root[N];

map <pii, int> ma;

struct node {
    int l, r, R, E, V;
} t[150*N], I = {0, 0, 0, 0, 0};
vector <pii> wh[N];

void Init() {
    for (int i = 1; i <= cnt; i++) t[i] = {0, 0, 0, 0, 0};
    cnt = 1;
}

node Merge(node n1, node n2, int x = 0) {
    node ne = I;
    ne.R = n1.R + n2.R;
    ne.E = n1.E + n2.E;
    ne.V = n1.V + n2.V;
    if (x) {
        ne.l = t[x].l;
        ne.r = t[x].r;
    }
    return ne;
}
void Add(int x, int y, int pos, int type, int lo = 0, int hi = N) {
    if (lo == hi) {
        t[x] = t[y];
        if (type == 0) t[x].R++;
        else if (type == 1) t[x].E++;
        else t[x].V++;
        return;
    }
    int mid = (lo + hi) / 2;
    if (pos <= mid) {
        t[x].l = ++cnt;
        t[x].r = t[y].r;
        Add(cnt, t[y].l, pos, type, lo, mid);
    }
    else {
        t[x].l = t[y].l;
        t[x].r = ++cnt;
        Add(cnt, t[y].r, pos, type, mid+1, hi);
    }
    t[x] = Merge(t[t[x].l], t[t[x].r], x);
}
void Add(int x, int pos, int type) {
    int y = ++cnt;
    Add(y, root[x], pos, type);
    root[x] = y;
}

node Query(int x, int a, int b, int lo = 0, int hi = N) {
    if (!x) return I;
    if (b < lo || hi < a) return I;
    if (a <= lo && hi <= b) return t[x];
    int mid = (lo + hi) / 2;
    return Merge(Query(t[x].l, a, b, lo, mid), Query(t[x].r, a, b, mid+1, hi));
}
node Get(int x, int y, int l, int r) {
    node X = I;
    node le = Query(root[x-1], l, r);
    node ri = Query(root[y], l, r);
    X.R = ri.R - le.R;
    X.E = ri.E - le.E;
    X.V = ri.V - le.V;
    return X;
}

void Dod(int x, int y) {
    int X = 2*x+1, Y = 2*y+1;
    
    wh[X].pb({Y, 0});

    wh[X-1].pb({Y, 1});
    wh[X+1].pb({Y, 1});
    wh[X].pb({Y-1, 1});
    wh[X].pb({Y+1, 1});

    wh[X-1].pb({Y+1, 2});
    wh[X+1].pb({Y+1, 2});
    wh[X-1].pb({Y-1, 2});
    wh[X+1].pb({Y-1, 2});
}

void init(int R, int C, int sr, int sc, int M, char *S) {
    Init();
    n = R; m = C;
    int dirx[100], diry[100];
    dirx['N'] = -1; diry['N'] = 0;
    dirx['E'] = 0; diry['E'] = 1;
    dirx['S'] = 1; diry['S'] = 0;
    dirx['W'] = 0; diry['W'] = -1;
    Dod(sc, sr);
    mnx = mxx = sr;
    mny = mxy = sc;
    for (int i = 0; i < M; i++) {
        sr += dirx[S[i]];
        sc += diry[S[i]];
        mnx = min(mnx, sr); mxx = max(mxx, sr);
        mny = min(mny, sc); mxy = max(mxy, sc);
        Dod(sc, sr);
    }
    for (int i = 1; i <= 2*C+2; i++) {
        root[i] = root[i-1];
        sort(all(wh[i]));
        wh[i].erase(unique(all(wh[i])), wh[i].end());
        for (int j = 0; j < wh[i].size(); j++) {
            Add(i, wh[i][j].F, wh[i][j].S);
        }
    }
}

int colour(int ar, int ac, int br, int bc) {
    int C = (ar >= mnx || br <= mxx || ac >= mny || bc <= mxy) ? 1 : 2;
    int x = 2*ac+1, y = 2*bc+1, l = 2*ar+1, r = 2*br+1;
    int nn = br - ar + 1, mm = bc - ac + 1;
    node X = Get(x, y, l, r);
    int R = X.R;
    int E = X.E + 2*nn + 2*mm;
    int V = X.V + 2*nn + 2*mm;
    return E - V + C - R;

    return 0;
}

Compilation message

rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:114:23: warning: array subscript has type 'char' [-Wchar-subscripts]
  114 |         sr += dirx[S[i]];
      |                       ^
rainbow.cpp:115:23: warning: array subscript has type 'char' [-Wchar-subscripts]
  115 |         sc += diry[S[i]];
      |                       ^
rainbow.cpp:124:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |         for (int j = 0; j < wh[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 5 ms 15196 KB Output is correct
3 Correct 3 ms 12888 KB Output is correct
4 Correct 4 ms 12888 KB Output is correct
5 Correct 6 ms 15448 KB Output is correct
6 Correct 3 ms 12888 KB Output is correct
7 Correct 3 ms 12888 KB Output is correct
8 Correct 2 ms 12892 KB Output is correct
9 Correct 3 ms 12888 KB Output is correct
10 Correct 2 ms 12888 KB Output is correct
11 Correct 4 ms 13144 KB Output is correct
12 Correct 6 ms 15448 KB Output is correct
13 Correct 5 ms 15192 KB Output is correct
14 Correct 7 ms 17756 KB Output is correct
15 Correct 3 ms 12888 KB Output is correct
16 Correct 3 ms 12888 KB Output is correct
17 Correct 3 ms 12888 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 3 ms 12888 KB Output is correct
3 Correct 176 ms 167212 KB Output is correct
4 Correct 277 ms 271644 KB Output is correct
5 Correct 254 ms 270008 KB Output is correct
6 Correct 225 ms 216524 KB Output is correct
7 Correct 220 ms 213892 KB Output is correct
8 Correct 108 ms 38296 KB Output is correct
9 Correct 236 ms 271408 KB Output is correct
10 Correct 264 ms 269844 KB Output is correct
11 Correct 212 ms 215876 KB Output is correct
12 Correct 202 ms 253084 KB Output is correct
13 Correct 202 ms 271220 KB Output is correct
14 Correct 213 ms 269844 KB Output is correct
15 Correct 191 ms 217872 KB Output is correct
16 Correct 200 ms 197284 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 143 ms 267744 KB Output is correct
3 Correct 202 ms 264636 KB Output is correct
4 Correct 161 ms 266260 KB Output is correct
5 Correct 141 ms 202644 KB Output is correct
6 Correct 76 ms 74836 KB Output is correct
7 Correct 102 ms 118612 KB Output is correct
8 Correct 136 ms 243756 KB Output is correct
9 Correct 126 ms 218708 KB Output is correct
10 Correct 47 ms 68484 KB Output is correct
11 Correct 102 ms 145372 KB Output is correct
12 Correct 149 ms 267792 KB Output is correct
13 Correct 197 ms 261764 KB Output is correct
14 Correct 147 ms 266068 KB Output is correct
15 Correct 147 ms 207124 KB Output is correct
16 Correct 73 ms 67044 KB Output is correct
17 Correct 97 ms 119004 KB Output is correct
18 Correct 161 ms 264824 KB Output is correct
19 Correct 170 ms 266132 KB Output is correct
20 Correct 169 ms 265328 KB Output is correct
21 Correct 138 ms 243596 KB Output is correct
22 Correct 130 ms 218964 KB Output is correct
23 Correct 47 ms 68224 KB Output is correct
24 Correct 100 ms 145488 KB Output is correct
25 Correct 151 ms 268116 KB Output is correct
26 Correct 192 ms 263944 KB Output is correct
27 Correct 152 ms 266096 KB Output is correct
28 Correct 138 ms 202544 KB Output is correct
29 Correct 73 ms 67064 KB Output is correct
30 Correct 96 ms 118840 KB Output is correct
31 Correct 162 ms 264788 KB Output is correct
32 Correct 176 ms 266920 KB Output is correct
33 Correct 168 ms 265880 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 5 ms 15196 KB Output is correct
3 Correct 3 ms 12888 KB Output is correct
4 Correct 4 ms 12888 KB Output is correct
5 Correct 6 ms 15448 KB Output is correct
6 Correct 3 ms 12888 KB Output is correct
7 Correct 3 ms 12888 KB Output is correct
8 Correct 2 ms 12892 KB Output is correct
9 Correct 3 ms 12888 KB Output is correct
10 Correct 2 ms 12888 KB Output is correct
11 Correct 4 ms 13144 KB Output is correct
12 Correct 6 ms 15448 KB Output is correct
13 Correct 5 ms 15192 KB Output is correct
14 Correct 7 ms 17756 KB Output is correct
15 Correct 3 ms 12888 KB Output is correct
16 Correct 3 ms 12888 KB Output is correct
17 Correct 3 ms 12888 KB Output is correct
18 Correct 270 ms 147164 KB Output is correct
19 Correct 93 ms 20560 KB Output is correct
20 Correct 94 ms 13676 KB Output is correct
21 Correct 95 ms 15692 KB Output is correct
22 Correct 97 ms 15820 KB Output is correct
23 Correct 118 ms 18288 KB Output is correct
24 Correct 90 ms 16208 KB Output is correct
25 Correct 94 ms 16084 KB Output is correct
26 Correct 97 ms 18236 KB Output is correct
27 Correct 191 ms 125520 KB Output is correct
28 Correct 152 ms 76628 KB Output is correct
29 Correct 173 ms 118928 KB Output is correct
30 Correct 263 ms 264460 KB Output is correct
31 Correct 5 ms 12888 KB Output is correct
32 Correct 223 ms 128080 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 5 ms 15196 KB Output is correct
3 Correct 3 ms 12888 KB Output is correct
4 Correct 4 ms 12888 KB Output is correct
5 Correct 6 ms 15448 KB Output is correct
6 Correct 3 ms 12888 KB Output is correct
7 Correct 3 ms 12888 KB Output is correct
8 Correct 2 ms 12892 KB Output is correct
9 Correct 3 ms 12888 KB Output is correct
10 Correct 2 ms 12888 KB Output is correct
11 Correct 4 ms 13144 KB Output is correct
12 Correct 6 ms 15448 KB Output is correct
13 Correct 5 ms 15192 KB Output is correct
14 Correct 7 ms 17756 KB Output is correct
15 Correct 3 ms 12888 KB Output is correct
16 Correct 3 ms 12888 KB Output is correct
17 Correct 3 ms 12888 KB Output is correct
18 Correct 270 ms 147164 KB Output is correct
19 Correct 93 ms 20560 KB Output is correct
20 Correct 94 ms 13676 KB Output is correct
21 Correct 95 ms 15692 KB Output is correct
22 Correct 97 ms 15820 KB Output is correct
23 Correct 118 ms 18288 KB Output is correct
24 Correct 90 ms 16208 KB Output is correct
25 Correct 94 ms 16084 KB Output is correct
26 Correct 97 ms 18236 KB Output is correct
27 Correct 191 ms 125520 KB Output is correct
28 Correct 152 ms 76628 KB Output is correct
29 Correct 173 ms 118928 KB Output is correct
30 Correct 263 ms 264460 KB Output is correct
31 Correct 5 ms 12888 KB Output is correct
32 Correct 223 ms 128080 KB Output is correct
33 Correct 143 ms 267744 KB Output is correct
34 Correct 202 ms 264636 KB Output is correct
35 Correct 161 ms 266260 KB Output is correct
36 Correct 141 ms 202644 KB Output is correct
37 Correct 76 ms 74836 KB Output is correct
38 Correct 102 ms 118612 KB Output is correct
39 Correct 136 ms 243756 KB Output is correct
40 Correct 126 ms 218708 KB Output is correct
41 Correct 47 ms 68484 KB Output is correct
42 Correct 102 ms 145372 KB Output is correct
43 Correct 149 ms 267792 KB Output is correct
44 Correct 197 ms 261764 KB Output is correct
45 Correct 147 ms 266068 KB Output is correct
46 Correct 147 ms 207124 KB Output is correct
47 Correct 73 ms 67044 KB Output is correct
48 Correct 97 ms 119004 KB Output is correct
49 Correct 161 ms 264824 KB Output is correct
50 Correct 170 ms 266132 KB Output is correct
51 Correct 169 ms 265328 KB Output is correct
52 Correct 138 ms 243596 KB Output is correct
53 Correct 130 ms 218964 KB Output is correct
54 Correct 47 ms 68224 KB Output is correct
55 Correct 100 ms 145488 KB Output is correct
56 Correct 151 ms 268116 KB Output is correct
57 Correct 192 ms 263944 KB Output is correct
58 Correct 152 ms 266096 KB Output is correct
59 Correct 138 ms 202544 KB Output is correct
60 Correct 73 ms 67064 KB Output is correct
61 Correct 96 ms 118840 KB Output is correct
62 Correct 162 ms 264788 KB Output is correct
63 Correct 176 ms 266920 KB Output is correct
64 Correct 168 ms 265880 KB Output is correct
65 Correct 176 ms 167212 KB Output is correct
66 Correct 277 ms 271644 KB Output is correct
67 Correct 254 ms 270008 KB Output is correct
68 Correct 225 ms 216524 KB Output is correct
69 Correct 220 ms 213892 KB Output is correct
70 Correct 108 ms 38296 KB Output is correct
71 Correct 236 ms 271408 KB Output is correct
72 Correct 264 ms 269844 KB Output is correct
73 Correct 212 ms 215876 KB Output is correct
74 Correct 202 ms 253084 KB Output is correct
75 Correct 202 ms 271220 KB Output is correct
76 Correct 213 ms 269844 KB Output is correct
77 Correct 191 ms 217872 KB Output is correct
78 Correct 200 ms 197284 KB Output is correct
79 Correct 294 ms 247204 KB Output is correct
80 Correct 285 ms 222316 KB Output is correct
81 Correct 143 ms 71656 KB Output is correct
82 Correct 222 ms 148732 KB Output is correct
83 Correct 204 ms 271188 KB Output is correct
84 Correct 275 ms 268656 KB Output is correct
85 Correct 213 ms 269652 KB Output is correct
86 Correct 207 ms 206048 KB Output is correct
87 Correct 122 ms 70472 KB Output is correct
88 Correct 145 ms 122708 KB Output is correct
89 Correct 211 ms 268300 KB Output is correct
90 Correct 256 ms 271760 KB Output is correct
91 Correct 260 ms 269380 KB Output is correct