oj.uz

Submission #392100

# Submission time Handle Problem Language Result Execution time Memory
392100 2021-04-20T13:56:21 Z MarcoMeijer Land of the Rainbow Gold (APIO17_rainbow) C++14
100 / 100
 2112 ms 146984 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;

// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e9
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
#define sz size()

const int MX = (1<<23);
const int N = (1<<18);

int R, C, sr, sc, m;
set<ii> blue;
set<ii> points;
set<ii> edges;
int minR, maxR, minC, maxC;

int root=0;

struct QuadTree {
    vi seg[N*2];
    int nxt2=1;

    void build() {
        RE(i,N*2) sort(all(seg[i]));
    }
    void add(int x, int y, int l=0, int r=N-1, int p=1) {
        if(x < l || x > r) return;
        seg[p].push_back(y);

        if(l == r) return;
        int m=(l+r)/2;
        add(x, y, l  , m, p*2  );
        add(x, y, m+1, r, p*2+1);
    }
    int get(int i, int j, int x, int y, int l=0, int r=N-1, int p=1) {
        if(j < l || i > r) return 0;
        if(i <= l && j >= r) {
            auto lb = lower_bound(all(seg[p]), x);
            auto ub = upper_bound(all(seg[p]), y);
            return ub - lb;
        }
        int m = (l+r)/2;
        int a = get(i, j, x, y, l  , m, p*2  );
        int b = get(i, j, x, y, m+1, r, p*2+1);
        return a+b;
    }
} blueCells, bluePoints, blueLandEdgesH, blueLandEdgesV;

void init(int _R, int _C, int _sr, int _sc, int M, char *S) {
    R=_R; C=_C; sr=_sr; sc=_sc;
    minR=maxR=sr;
    minC=maxC=sc;
    RE(i,M) {
        blue.insert({sc,sr});
        if(S[i] == 'N') sr--;
        if(S[i] == 'S') sr++;
        if(S[i] == 'E') sc++;
        if(S[i] == 'W') sc--;
    }
    blue.insert({sc,sr});

    FOR(p,blue) {
        minR = min(minR, p.se);
        minC = min(minC, p.fi);
        maxR = max(maxR, p.se);
        maxC = max(maxC, p.fi);
        blueCells.add(p.fi,p.se);
        points.insert({p.fi  ,p.se  });
        points.insert({p.fi  ,p.se+1});
        points.insert({p.fi+1,p.se  });
        points.insert({p.fi+1,p.se+1});

        if(!blue.count({p.fi-1,p.se  })) blueLandEdgesV.add(p.fi  , p.se  );
                                         blueLandEdgesV.add(p.fi+1, p.se  );
        if(!blue.count({p.fi  ,p.se-1})) blueLandEdgesH.add(p.fi  , p.se  );
                                         blueLandEdgesH.add(p.fi  , p.se+1);
    }

    FOR(p,points)
        bluePoints.add(p.fi,p.se);

    blueCells.build();
    bluePoints.build();
    blueLandEdgesH.build();
    blueLandEdgesV.build();
}

int colour(int ar, int ac, int br, int bc) {
    int blueCellsCnt  = blueCells .get(ac  ,bc,ar  ,br);
    int bluePointsCnt = bluePoints.get(ac+1,bc,ar+1,br);
    int blueLandEdges = blueLandEdgesH.get(ac,bc,ar+1,br) + blueLandEdgesV.get(ac+1,bc,ar,br);
    int W = bc - ac + 1;
    int H = br - ar + 1;
    int V = W*H - blueCellsCnt;
    int F = (W-1)*(H-1) - bluePointsCnt + 1;
    int E = (W-1)*H + (H-1)*W - blueLandEdges;

    if(ar < minR && maxR < br && ac < minC && maxC < bc)
        F++;

    return V - E + F - 1;
}

Compilation message

rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:96:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   96 |         if(!blue.count({p.fi-1,p.se  })) blueLandEdgesV.add(p.fi  , p.se  );
      |         ^~
rainbow.cpp:97:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   97 |                                          blueLandEdgesV.add(p.fi+1, p.se  );
      |                                          ^~~~~~~~~~~~~~
rainbow.cpp:98:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   98 |         if(!blue.count({p.fi  ,p.se-1})) blueLandEdgesH.add(p.fi  , p.se  );
      |         ^~
rainbow.cpp:99:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   99 |                                          blueLandEdgesH.add(p.fi  , p.se+1);
      |                                          ^~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 49612 KB Output is correct
2 Correct 46 ms 50064 KB Output is correct
3 Correct 41 ms 49684 KB Output is correct
4 Correct 42 ms 49720 KB Output is correct
5 Correct 52 ms 50292 KB Output is correct
6 Correct 36 ms 49524 KB Output is correct
7 Correct 36 ms 49444 KB Output is correct
8 Correct 36 ms 49444 KB Output is correct
9 Correct 36 ms 49500 KB Output is correct
10 Correct 36 ms 49484 KB Output is correct
11 Correct 42 ms 49688 KB Output is correct
12 Correct 47 ms 49868 KB Output is correct
13 Correct 49 ms 50436 KB Output is correct
14 Correct 48 ms 50668 KB Output is correct
15 Correct 37 ms 49484 KB Output is correct
16 Correct 36 ms 49440 KB Output is correct
17 Correct 37 ms 49556 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 49440 KB Output is correct
2 Correct 37 ms 49556 KB Output is correct
3 Correct 1164 ms 97524 KB Output is correct
4 Correct 1845 ms 144876 KB Output is correct
5 Correct 1791 ms 144864 KB Output is correct
6 Correct 1278 ms 112676 KB Output is correct
7 Correct 1387 ms 111636 KB Output is correct
8 Correct 441 ms 53200 KB Output is correct
9 Correct 1951 ms 146984 KB Output is correct
10 Correct 1835 ms 144672 KB Output is correct
11 Correct 1334 ms 112488 KB Output is correct
12 Correct 1018 ms 127372 KB Output is correct
13 Correct 1229 ms 146884 KB Output is correct
14 Correct 1294 ms 144716 KB Output is correct
15 Correct 1051 ms 112476 KB Output is correct
16 Correct 1233 ms 108716 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 49484 KB Output is correct
2 Correct 679 ms 126088 KB Output is correct
3 Correct 835 ms 113492 KB Output is correct
4 Correct 628 ms 120424 KB Output is correct
5 Correct 754 ms 100012 KB Output is correct
6 Correct 170 ms 62276 KB Output is correct
7 Correct 296 ms 74316 KB Output is correct
8 Correct 610 ms 121024 KB Output is correct
9 Correct 540 ms 109100 KB Output is correct
10 Correct 164 ms 64304 KB Output is correct
11 Correct 350 ms 86000 KB Output is correct
12 Correct 679 ms 126080 KB Output is correct
13 Correct 819 ms 113560 KB Output is correct
14 Correct 627 ms 120472 KB Output is correct
15 Correct 796 ms 99992 KB Output is correct
16 Correct 144 ms 60128 KB Output is correct
17 Correct 308 ms 73972 KB Output is correct
18 Correct 685 ms 113700 KB Output is correct
19 Correct 762 ms 118832 KB Output is correct
20 Correct 764 ms 118804 KB Output is correct
21 Correct 584 ms 121172 KB Output is correct
22 Correct 542 ms 109104 KB Output is correct
23 Correct 164 ms 64408 KB Output is correct
24 Correct 348 ms 86072 KB Output is correct
25 Correct 698 ms 126208 KB Output is correct
26 Correct 825 ms 113432 KB Output is correct
27 Correct 620 ms 120456 KB Output is correct
28 Correct 762 ms 99988 KB Output is correct
29 Correct 144 ms 60040 KB Output is correct
30 Correct 298 ms 73840 KB Output is correct
31 Correct 692 ms 113872 KB Output is correct
32 Correct 756 ms 118992 KB Output is correct
33 Correct 759 ms 118780 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 49612 KB Output is correct
2 Correct 46 ms 50064 KB Output is correct
3 Correct 41 ms 49684 KB Output is correct
4 Correct 42 ms 49720 KB Output is correct
5 Correct 52 ms 50292 KB Output is correct
6 Correct 36 ms 49524 KB Output is correct
7 Correct 36 ms 49444 KB Output is correct
8 Correct 36 ms 49444 KB Output is correct
9 Correct 36 ms 49500 KB Output is correct
10 Correct 36 ms 49484 KB Output is correct
11 Correct 42 ms 49688 KB Output is correct
12 Correct 47 ms 49868 KB Output is correct
13 Correct 49 ms 50436 KB Output is correct
14 Correct 48 ms 50668 KB Output is correct
15 Correct 37 ms 49484 KB Output is correct
16 Correct 36 ms 49440 KB Output is correct
17 Correct 37 ms 49556 KB Output is correct
18 Correct 1186 ms 83704 KB Output is correct
19 Correct 348 ms 54680 KB Output is correct
20 Correct 246 ms 53188 KB Output is correct
21 Correct 267 ms 53576 KB Output is correct
22 Correct 321 ms 53832 KB Output is correct
23 Correct 336 ms 54596 KB Output is correct
24 Correct 299 ms 53532 KB Output is correct
25 Correct 320 ms 53896 KB Output is correct
26 Correct 299 ms 54076 KB Output is correct
27 Correct 710 ms 81720 KB Output is correct
28 Correct 539 ms 66372 KB Output is correct
29 Correct 746 ms 77684 KB Output is correct
30 Correct 1366 ms 117296 KB Output is correct
31 Correct 41 ms 49612 KB Output is correct
32 Correct 996 ms 83984 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 49612 KB Output is correct
2 Correct 46 ms 50064 KB Output is correct
3 Correct 41 ms 49684 KB Output is correct
4 Correct 42 ms 49720 KB Output is correct
5 Correct 52 ms 50292 KB Output is correct
6 Correct 36 ms 49524 KB Output is correct
7 Correct 36 ms 49444 KB Output is correct
8 Correct 36 ms 49444 KB Output is correct
9 Correct 36 ms 49500 KB Output is correct
10 Correct 36 ms 49484 KB Output is correct
11 Correct 42 ms 49688 KB Output is correct
12 Correct 47 ms 49868 KB Output is correct
13 Correct 49 ms 50436 KB Output is correct
14 Correct 48 ms 50668 KB Output is correct
15 Correct 37 ms 49484 KB Output is correct
16 Correct 36 ms 49440 KB Output is correct
17 Correct 37 ms 49556 KB Output is correct
18 Correct 1186 ms 83704 KB Output is correct
19 Correct 348 ms 54680 KB Output is correct
20 Correct 246 ms 53188 KB Output is correct
21 Correct 267 ms 53576 KB Output is correct
22 Correct 321 ms 53832 KB Output is correct
23 Correct 336 ms 54596 KB Output is correct
24 Correct 299 ms 53532 KB Output is correct
25 Correct 320 ms 53896 KB Output is correct
26 Correct 299 ms 54076 KB Output is correct
27 Correct 710 ms 81720 KB Output is correct
28 Correct 539 ms 66372 KB Output is correct
29 Correct 746 ms 77684 KB Output is correct
30 Correct 1366 ms 117296 KB Output is correct
31 Correct 41 ms 49612 KB Output is correct
32 Correct 996 ms 83984 KB Output is correct
33 Correct 679 ms 126088 KB Output is correct
34 Correct 835 ms 113492 KB Output is correct
35 Correct 628 ms 120424 KB Output is correct
36 Correct 754 ms 100012 KB Output is correct
37 Correct 170 ms 62276 KB Output is correct
38 Correct 296 ms 74316 KB Output is correct
39 Correct 610 ms 121024 KB Output is correct
40 Correct 540 ms 109100 KB Output is correct
41 Correct 164 ms 64304 KB Output is correct
42 Correct 350 ms 86000 KB Output is correct
43 Correct 679 ms 126080 KB Output is correct
44 Correct 819 ms 113560 KB Output is correct
45 Correct 627 ms 120472 KB Output is correct
46 Correct 796 ms 99992 KB Output is correct
47 Correct 144 ms 60128 KB Output is correct
48 Correct 308 ms 73972 KB Output is correct
49 Correct 685 ms 113700 KB Output is correct
50 Correct 762 ms 118832 KB Output is correct
51 Correct 764 ms 118804 KB Output is correct
52 Correct 584 ms 121172 KB Output is correct
53 Correct 542 ms 109104 KB Output is correct
54 Correct 164 ms 64408 KB Output is correct
55 Correct 348 ms 86072 KB Output is correct
56 Correct 698 ms 126208 KB Output is correct
57 Correct 825 ms 113432 KB Output is correct
58 Correct 620 ms 120456 KB Output is correct
59 Correct 762 ms 99988 KB Output is correct
60 Correct 144 ms 60040 KB Output is correct
61 Correct 298 ms 73840 KB Output is correct
62 Correct 692 ms 113872 KB Output is correct
63 Correct 756 ms 118992 KB Output is correct
64 Correct 759 ms 118780 KB Output is correct
65 Correct 1164 ms 97524 KB Output is correct
66 Correct 1845 ms 144876 KB Output is correct
67 Correct 1791 ms 144864 KB Output is correct
68 Correct 1278 ms 112676 KB Output is correct
69 Correct 1387 ms 111636 KB Output is correct
70 Correct 441 ms 53200 KB Output is correct
71 Correct 1951 ms 146984 KB Output is correct
72 Correct 1835 ms 144672 KB Output is correct
73 Correct 1334 ms 112488 KB Output is correct
74 Correct 1018 ms 127372 KB Output is correct
75 Correct 1229 ms 146884 KB Output is correct
76 Correct 1294 ms 144716 KB Output is correct
77 Correct 1051 ms 112476 KB Output is correct
78 Correct 1233 ms 108716 KB Output is correct
79 Correct 2112 ms 124704 KB Output is correct
80 Correct 2055 ms 112680 KB Output is correct
81 Correct 844 ms 67956 KB Output is correct
82 Correct 1268 ms 89640 KB Output is correct
83 Correct 1581 ms 129708 KB Output is correct
84 Correct 1273 ms 117260 KB Output is correct
85 Correct 1138 ms 124060 KB Output is correct
86 Correct 1240 ms 103560 KB Output is correct
87 Correct 546 ms 63840 KB Output is correct
88 Correct 722 ms 77528 KB Output is correct
89 Correct 1071 ms 117412 KB Output is correct
90 Correct 1442 ms 122396 KB Output is correct
91 Correct 1511 ms 122336 KB Output is correct