oj.uz

Submission #431854

# Submission time Handle Problem Language Result Execution time Memory
431854 2021-06-17T16:09:21 Z nvmdava Land of the Rainbow Gold (APIO17_rainbow) C++17
100 / 100
 1650 ms 414588 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define ll long long
const int N = 200005;

struct Node{
    Node *l = NULL, *r = NULL;
    ll a;
    Node* update(int L, int R, int x){
        Node* res = new Node();
        res -> l = l;
        res -> r = r;
        res -> a = a;
        ++res -> a;
        if(L == R)
            return res;
        
        int m = (L + R) >> 1;
        if(x <= m){
            if(l == NULL)
                l = new Node();
            res -> l = l -> update(L, m, x);
        } else {
            if(r == NULL)
                r = new Node();
            res -> r = r -> update(m + 1, R, x);
        }
        return res;
    }
    ll query(int L, int R, int le, int ri){
        if(R < le || L > ri)
            return 0;
        if(le <= L && R <= ri)
            return a;
        int m = (L + R) >> 1;

        return (l == NULL ? 0 : l -> query(L, m, le, ri)) + (r == NULL ? 0 : r -> query(m + 1, R, le, ri));
    }
};

struct Grid{
    Node* seg[N];
    void build(set<pair<int, int> >& v){
        seg[0] = new Node();
        auto it = v.begin();
        for(int i = 1; i < N; ++i){
            seg[i] = seg[i - 1];
            while(it != v.end() && it -> ff == i){
                seg[i] = seg[i] -> update(1, N, it -> ss);
                ++it;
            }
        }
    }
    ll query(int x1, int y1, int x2, int y2){
        if(x1 > x2 || y1 > y2) return 0; 
        return seg[x2] -> query(1, N, y1, y2) - seg[x1 - 1] -> query(1, N, y1, y2);
    }
} riv, dot, lix, liy;
int mnx, mny, mxx, mxy;
void init(int R, int C, int sr, int sc, int M, char *S) {
    set<pair<int, int> > rivs, dots, lixs, liys;
    rivs.insert({sr, sc});
    mnx = mxx = sr;
    mny = mxy = sc;
    for(int i = 0; i < M; ++i){
        if(S[i] == 'N')
            --sr;
        if(S[i] == 'E')
            ++sc;
        if(S[i] == 'S')
            ++sr;
        if(S[i] == 'W')
            --sc;
        rivs.insert({sr, sc});
        mnx = min(mnx, sr);
        mxx = max(mxx, sr);
        mny = min(mny, sc);
        mxy = max(mxy, sc);
    }
    for(auto& a : rivs){
        dots.insert({a.ff, a.ss});
        dots.insert({a.ff, a.ss + 1});
        dots.insert({a.ff + 1, a.ss + 1});
        dots.insert({a.ff + 1, a.ss});
        lixs.insert({a.ff, a.ss});
        lixs.insert({a.ff, a.ss + 1});
        liys.insert({a.ff, a.ss});
        liys.insert({a.ff + 1, a.ss});
    }
    riv.build(rivs);
    dot.build(dots);
    lix.build(lixs);
    liy.build(liys);
}

int colour(int x1, int y1, int x2, int y2){
    return (x1 < mnx && mxx < x2 && y1 < mny && mxy < y2) + 1 - riv.query(x1, y1, x2, y2) - dot.query(x1 + 1, y1 + 1, x2, y2) + lix.query(x1, y1 + 1, x2, y2) + liy.query(x1 + 1, y1, x2, y2);
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7116 KB Output is correct
2 Correct 13 ms 9576 KB Output is correct
3 Correct 9 ms 7244 KB Output is correct
4 Correct 9 ms 7500 KB Output is correct
5 Correct 14 ms 10264 KB Output is correct
6 Correct 7 ms 6476 KB Output is correct
7 Correct 6 ms 6476 KB Output is correct
8 Correct 5 ms 6500 KB Output is correct
9 Correct 6 ms 6524 KB Output is correct
10 Correct 6 ms 6476 KB Output is correct
11 Correct 9 ms 7740 KB Output is correct
12 Correct 11 ms 8908 KB Output is correct
13 Correct 16 ms 11544 KB Output is correct
14 Correct 18 ms 12624 KB Output is correct
15 Correct 6 ms 6448 KB Output is correct
16 Correct 6 ms 6476 KB Output is correct
17 Correct 6 ms 6476 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6476 KB Output is correct
2 Correct 6 ms 6476 KB Output is correct
3 Correct 656 ms 248292 KB Output is correct
4 Correct 1084 ms 410924 KB Output is correct
5 Correct 1058 ms 405852 KB Output is correct
6 Correct 770 ms 309380 KB Output is correct
7 Correct 933 ms 304324 KB Output is correct
8 Correct 74 ms 7236 KB Output is correct
9 Correct 1098 ms 410848 KB Output is correct
10 Correct 1128 ms 405808 KB Output is correct
11 Correct 835 ms 309264 KB Output is correct
12 Correct 769 ms 383080 KB Output is correct
13 Correct 839 ms 410768 KB Output is correct
14 Correct 841 ms 405880 KB Output is correct
15 Correct 691 ms 309828 KB Output is correct
16 Correct 742 ms 292728 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6448 KB Output is correct
2 Correct 763 ms 411096 KB Output is correct
3 Correct 672 ms 379332 KB Output is correct
4 Correct 733 ms 398540 KB Output is correct
5 Correct 508 ms 293996 KB Output is correct
6 Correct 141 ms 77636 KB Output is correct
7 Correct 273 ms 148288 KB Output is correct
8 Correct 686 ms 355140 KB Output is correct
9 Correct 612 ms 314564 KB Output is correct
10 Correct 146 ms 82064 KB Output is correct
11 Correct 350 ms 197216 KB Output is correct
12 Correct 749 ms 411032 KB Output is correct
13 Correct 668 ms 379220 KB Output is correct
14 Correct 718 ms 398580 KB Output is correct
15 Correct 529 ms 294076 KB Output is correct
16 Correct 116 ms 63356 KB Output is correct
17 Correct 277 ms 148384 KB Output is correct
18 Correct 673 ms 386116 KB Output is correct
19 Correct 732 ms 401384 KB Output is correct
20 Correct 733 ms 401216 KB Output is correct
21 Correct 699 ms 355056 KB Output is correct
22 Correct 621 ms 314568 KB Output is correct
23 Correct 143 ms 82100 KB Output is correct
24 Correct 363 ms 197008 KB Output is correct
25 Correct 781 ms 411152 KB Output is correct
26 Correct 657 ms 379336 KB Output is correct
27 Correct 790 ms 398592 KB Output is correct
28 Correct 511 ms 294180 KB Output is correct
29 Correct 112 ms 63432 KB Output is correct
30 Correct 266 ms 148460 KB Output is correct
31 Correct 685 ms 386192 KB Output is correct
32 Correct 734 ms 401376 KB Output is correct
33 Correct 735 ms 401128 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7116 KB Output is correct
2 Correct 13 ms 9576 KB Output is correct
3 Correct 9 ms 7244 KB Output is correct
4 Correct 9 ms 7500 KB Output is correct
5 Correct 14 ms 10264 KB Output is correct
6 Correct 7 ms 6476 KB Output is correct
7 Correct 6 ms 6476 KB Output is correct
8 Correct 5 ms 6500 KB Output is correct
9 Correct 6 ms 6524 KB Output is correct
10 Correct 6 ms 6476 KB Output is correct
11 Correct 9 ms 7740 KB Output is correct
12 Correct 11 ms 8908 KB Output is correct
13 Correct 16 ms 11544 KB Output is correct
14 Correct 18 ms 12624 KB Output is correct
15 Correct 6 ms 6448 KB Output is correct
16 Correct 6 ms 6476 KB Output is correct
17 Correct 6 ms 6476 KB Output is correct
18 Correct 1262 ms 201744 KB Output is correct
19 Correct 317 ms 18752 KB Output is correct
20 Correct 209 ms 11460 KB Output is correct
21 Correct 242 ms 12988 KB Output is correct
22 Correct 272 ms 14740 KB Output is correct
23 Correct 321 ms 18620 KB Output is correct
24 Correct 217 ms 12612 KB Output is correct
25 Correct 241 ms 14236 KB Output is correct
26 Correct 265 ms 15740 KB Output is correct
27 Correct 506 ms 164872 KB Output is correct
28 Correct 363 ms 84464 KB Output is correct
29 Correct 496 ms 151388 KB Output is correct
30 Correct 1080 ms 389852 KB Output is correct
31 Correct 10 ms 6788 KB Output is correct
32 Correct 919 ms 166704 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7116 KB Output is correct
2 Correct 13 ms 9576 KB Output is correct
3 Correct 9 ms 7244 KB Output is correct
4 Correct 9 ms 7500 KB Output is correct
5 Correct 14 ms 10264 KB Output is correct
6 Correct 7 ms 6476 KB Output is correct
7 Correct 6 ms 6476 KB Output is correct
8 Correct 5 ms 6500 KB Output is correct
9 Correct 6 ms 6524 KB Output is correct
10 Correct 6 ms 6476 KB Output is correct
11 Correct 9 ms 7740 KB Output is correct
12 Correct 11 ms 8908 KB Output is correct
13 Correct 16 ms 11544 KB Output is correct
14 Correct 18 ms 12624 KB Output is correct
15 Correct 6 ms 6448 KB Output is correct
16 Correct 6 ms 6476 KB Output is correct
17 Correct 6 ms 6476 KB Output is correct
18 Correct 1262 ms 201744 KB Output is correct
19 Correct 317 ms 18752 KB Output is correct
20 Correct 209 ms 11460 KB Output is correct
21 Correct 242 ms 12988 KB Output is correct
22 Correct 272 ms 14740 KB Output is correct
23 Correct 321 ms 18620 KB Output is correct
24 Correct 217 ms 12612 KB Output is correct
25 Correct 241 ms 14236 KB Output is correct
26 Correct 265 ms 15740 KB Output is correct
27 Correct 506 ms 164872 KB Output is correct
28 Correct 363 ms 84464 KB Output is correct
29 Correct 496 ms 151388 KB Output is correct
30 Correct 1080 ms 389852 KB Output is correct
31 Correct 10 ms 6788 KB Output is correct
32 Correct 919 ms 166704 KB Output is correct
33 Correct 763 ms 411096 KB Output is correct
34 Correct 672 ms 379332 KB Output is correct
35 Correct 733 ms 398540 KB Output is correct
36 Correct 508 ms 293996 KB Output is correct
37 Correct 141 ms 77636 KB Output is correct
38 Correct 273 ms 148288 KB Output is correct
39 Correct 686 ms 355140 KB Output is correct
40 Correct 612 ms 314564 KB Output is correct
41 Correct 146 ms 82064 KB Output is correct
42 Correct 350 ms 197216 KB Output is correct
43 Correct 749 ms 411032 KB Output is correct
44 Correct 668 ms 379220 KB Output is correct
45 Correct 718 ms 398580 KB Output is correct
46 Correct 529 ms 294076 KB Output is correct
47 Correct 116 ms 63356 KB Output is correct
48 Correct 277 ms 148384 KB Output is correct
49 Correct 673 ms 386116 KB Output is correct
50 Correct 732 ms 401384 KB Output is correct
51 Correct 733 ms 401216 KB Output is correct
52 Correct 699 ms 355056 KB Output is correct
53 Correct 621 ms 314568 KB Output is correct
54 Correct 143 ms 82100 KB Output is correct
55 Correct 363 ms 197008 KB Output is correct
56 Correct 781 ms 411152 KB Output is correct
57 Correct 657 ms 379336 KB Output is correct
58 Correct 790 ms 398592 KB Output is correct
59 Correct 511 ms 294180 KB Output is correct
60 Correct 112 ms 63432 KB Output is correct
61 Correct 266 ms 148460 KB Output is correct
62 Correct 685 ms 386192 KB Output is correct
63 Correct 734 ms 401376 KB Output is correct
64 Correct 735 ms 401128 KB Output is correct
65 Correct 656 ms 248292 KB Output is correct
66 Correct 1084 ms 410924 KB Output is correct
67 Correct 1058 ms 405852 KB Output is correct
68 Correct 770 ms 309380 KB Output is correct
69 Correct 933 ms 304324 KB Output is correct
70 Correct 74 ms 7236 KB Output is correct
71 Correct 1098 ms 410848 KB Output is correct
72 Correct 1128 ms 405808 KB Output is correct
73 Correct 835 ms 309264 KB Output is correct
74 Correct 769 ms 383080 KB Output is correct
75 Correct 839 ms 410768 KB Output is correct
76 Correct 841 ms 405880 KB Output is correct
77 Correct 691 ms 309828 KB Output is correct
78 Correct 742 ms 292728 KB Output is correct
79 Correct 1638 ms 358584 KB Output is correct
80 Correct 1650 ms 317964 KB Output is correct
81 Correct 570 ms 85500 KB Output is correct
82 Correct 626 ms 200568 KB Output is correct
83 Correct 1155 ms 414588 KB Output is correct
84 Correct 825 ms 382776 KB Output is correct
85 Correct 942 ms 402028 KB Output is correct
86 Correct 706 ms 297580 KB Output is correct
87 Correct 220 ms 66984 KB Output is correct
88 Correct 369 ms 152032 KB Output is correct
89 Correct 801 ms 389692 KB Output is correct
90 Correct 1089 ms 404848 KB Output is correct
91 Correct 1047 ms 404708 KB Output is correct