oj.uz

Submission #593974

# Submission time Handle Problem Language Result Execution time Memory
593974 2022-07-11T18:40:22 Z czhang2718 Land of the Rainbow Gold (APIO17_rainbow) C++17
100 / 100
 1444 ms 263688 KB 
#include "bits/stdc++.h"
#include "rainbow.h"
using namespace std;

int r, c, sx, sy, m;
string s;
int lx, ly, rx, ry;
vector<pair<int,int>> g, ex, ey, two;



struct wavelet{
    int n;
    vector<vector<int>> vec, cnt;
    vector<int> X, Y;

    wavelet(){
    }

    void init(vector<pair<int,int>> v){
        n=v.size();
        vec.resize(4*n);
        cnt.resize(4*n);
        for(auto p:v) X.push_back(p.first), Y.push_back(p.second);
        sort(X.begin(), X.end()); 
        sort(Y.begin(), Y.end());
        Y.erase(unique(Y.begin(), Y.end()), Y.end());
        sort(v.begin(), v.end());
        for(auto p:v){
            vec[0].push_back(lower_bound(Y.begin(), Y.end(), p.second)-Y.begin());
        }
        build(0, 0, Y.size());
    }

    void build(int x, int l, int r){
        if(r<=l+1) return;
        int m=(l+r)/2;
        cnt[x].resize(vec[x].size());
        for(int i=0; i<vec[x].size(); i++){
            cnt[x][i]=(i?cnt[x][i-1]:0)+(vec[x][i]<m);
            vec[2*x+1+(vec[x][i]>=m)].push_back(vec[x][i]);
        }
        build(2*x+1, l, m);
        build(2*x+2, m, r);
    }

    int query(int x, int l, int r, int li, int ri, int a, int b){ // ind [l,r] vals [a,b)
        if(l>=a && r<=b) return ri-li+1;
        if(l>=b || r<=a || ri<li) return 0;
        int m=(l+r)/2;
        int left_li=cnt[x][li]-(vec[x][li]<m);
        int left_ri=cnt[x][ri]-1;
        int right_li=li-cnt[x][li]+(vec[x][li]<m);
        int right_ri=ri-cnt[x][ri];
        return query(2*x+1, l, m, left_li, left_ri, a, b) + query(2*x+2, m, r, right_li, right_ri, a, b);
    }

    int rect(int a, int c, int b, int d){
        if(b<a || d<c) return 0;
        a=lower_bound(X.begin(), X.end(), a)-X.begin();
        b=upper_bound(X.begin(), X.end(), b)-X.begin()-1;
        c=lower_bound(Y.begin(), Y.end(), c)-Y.begin();
        d=upper_bound(Y.begin(), Y.end(), d)-Y.begin();
        return query(0, 0, Y.size(), a, b, c, d);
    }
};






wavelet w_ex, w_ey, w_g, w_two;
int dx[]={0, 0, 1, 1};
int dy[]={0, 1, 0, 1};



void init(int R, int C, int sr, int sc, int M, char *S) {
    s=S;
    int x=sr, y=sc;
    lx=rx=x;
    ly=ry=y;
    map<pair<int,int>,bool> mp;
    g.push_back({x,y});
    mp[{x,y}]=1;
    for(char c:s){
        if(c=='N') x--;
        if(c=='S') x++;
        if(c=='W') y--;
        if(c=='E') y++;
        g.push_back({x,y});
        mp[{x,y}]=1;
        lx=min(lx, x);
        rx=max(rx, x);
        ly=min(ly, y);
        ry=max(ry, y);
    }
    sort(g.begin(), g.end());
    g.erase(unique(g.begin(), g.end()), g.end());

    for(auto p:g){
        int x=p.first, y=p.second;
        for(int k=0; k<4; k++){
            x+=dx[k]; y+=dy[k];
            if(mp[{x,y-1}] || mp[{x-1,y}] || mp[{x-1,y-1}] || mp[{x,y}]) two.push_back({x,y});
            if(mp[{x-1, y}] || mp[{x,y}]) ex.push_back({x,y});
            if(mp[{x, y-1}] || mp[{x,y}]) ey.push_back({x,y});
            x-=dx[k]; y-=dy[k];
        }
    }
    sort(ex.begin(), ex.end());
    sort(ey.begin(), ey.end());
    sort(two.begin(), two.end());
    ex.erase(unique(ex.begin(), ex.end()), ex.end());
    ey.erase(unique(ey.begin(), ey.end()), ey.end());
    two.erase(unique(two.begin(), two.end()), two.end());
    w_ex.init(ex);
    w_ey.init(ey);
    w_g.init(g);
    w_two.init(two);
}



int colour(int ar, int ac, int br, int bc) {
    int V=(br-ar+1)*(bc-ac+1)-w_g.rect(ar, ac, br, bc);
    int E=(br-ar+1)*(bc-ac)+(br-ar)*(bc-ac+1)-w_ex.rect(ar+1,ac,br,bc)-w_ey.rect(ar,ac+1,br,bc);
    int F=(br-ar)*(bc-ac)-w_two.rect(ar+1,ac+1,br,bc)+(ar<lx&&br>rx&&ac<ly&&bc>ry);
    // cout << V << "-" << E << "+" << F<< '\n';
    return V-E+F;
}
// add 1 face if rectangles covers region!

Compilation message

rainbow.cpp: In member function 'void wavelet::build(int, int, int)':
rainbow.cpp:39:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         for(int i=0; i<vec[x].size(); i++){
      |                      ~^~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 7 ms 1748 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 3 ms 724 KB Output is correct
5 Correct 6 ms 2132 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 3 ms 832 KB Output is correct
12 Correct 4 ms 1344 KB Output is correct
13 Correct 8 ms 2692 KB Output is correct
14 Correct 8 ms 3176 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 308 KB Output is correct
17 Correct 1 ms 212 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 681 ms 153216 KB Output is correct
4 Correct 1210 ms 262900 KB Output is correct
5 Correct 1135 ms 258692 KB Output is correct
6 Correct 743 ms 196712 KB Output is correct
7 Correct 924 ms 189992 KB Output is correct
8 Correct 66 ms 4936 KB Output is correct
9 Correct 1105 ms 262824 KB Output is correct
10 Correct 1130 ms 258580 KB Output is correct
11 Correct 824 ms 196820 KB Output is correct
12 Correct 800 ms 246664 KB Output is correct
13 Correct 820 ms 262932 KB Output is correct
14 Correct 764 ms 258584 KB Output is correct
15 Correct 575 ms 196912 KB Output is correct
16 Correct 787 ms 192544 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 812 ms 260088 KB Output is correct
3 Correct 355 ms 153928 KB Output is correct
4 Correct 600 ms 245908 KB Output is correct
5 Correct 410 ms 171696 KB Output is correct
6 Correct 89 ms 36928 KB Output is correct
7 Correct 171 ms 73540 KB Output is correct
8 Correct 540 ms 216200 KB Output is correct
9 Correct 511 ms 189784 KB Output is correct
10 Correct 100 ms 42124 KB Output is correct
11 Correct 297 ms 116492 KB Output is correct
12 Correct 862 ms 260128 KB Output is correct
13 Correct 355 ms 153812 KB Output is correct
14 Correct 644 ms 245928 KB Output is correct
15 Correct 420 ms 171712 KB Output is correct
16 Correct 101 ms 30564 KB Output is correct
17 Correct 168 ms 71620 KB Output is correct
18 Correct 416 ms 190112 KB Output is correct
19 Correct 653 ms 238616 KB Output is correct
20 Correct 628 ms 238464 KB Output is correct
21 Correct 546 ms 216196 KB Output is correct
22 Correct 482 ms 189828 KB Output is correct
23 Correct 105 ms 42108 KB Output is correct
24 Correct 286 ms 116516 KB Output is correct
25 Correct 806 ms 260136 KB Output is correct
26 Correct 374 ms 153768 KB Output is correct
27 Correct 587 ms 245864 KB Output is correct
28 Correct 419 ms 171652 KB Output is correct
29 Correct 76 ms 30564 KB Output is correct
30 Correct 170 ms 71580 KB Output is correct
31 Correct 409 ms 190056 KB Output is correct
32 Correct 649 ms 238588 KB Output is correct
33 Correct 597 ms 238544 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 7 ms 1748 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 3 ms 724 KB Output is correct
5 Correct 6 ms 2132 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 3 ms 832 KB Output is correct
12 Correct 4 ms 1344 KB Output is correct
13 Correct 8 ms 2692 KB Output is correct
14 Correct 8 ms 3176 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 308 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 922 ms 106320 KB Output is correct
19 Correct 234 ms 8564 KB Output is correct
20 Correct 144 ms 4396 KB Output is correct
21 Correct 161 ms 5308 KB Output is correct
22 Correct 190 ms 6200 KB Output is correct
23 Correct 197 ms 8396 KB Output is correct
24 Correct 163 ms 5012 KB Output is correct
25 Correct 195 ms 5964 KB Output is correct
26 Correct 186 ms 6752 KB Output is correct
27 Correct 371 ms 82500 KB Output is correct
28 Correct 334 ms 42940 KB Output is correct
29 Correct 366 ms 77008 KB Output is correct
30 Correct 804 ms 193576 KB Output is correct
31 Correct 3 ms 468 KB Output is correct
32 Correct 690 ms 84636 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 7 ms 1748 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 3 ms 724 KB Output is correct
5 Correct 6 ms 2132 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 3 ms 832 KB Output is correct
12 Correct 4 ms 1344 KB Output is correct
13 Correct 8 ms 2692 KB Output is correct
14 Correct 8 ms 3176 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 308 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 922 ms 106320 KB Output is correct
19 Correct 234 ms 8564 KB Output is correct
20 Correct 144 ms 4396 KB Output is correct
21 Correct 161 ms 5308 KB Output is correct
22 Correct 190 ms 6200 KB Output is correct
23 Correct 197 ms 8396 KB Output is correct
24 Correct 163 ms 5012 KB Output is correct
25 Correct 195 ms 5964 KB Output is correct
26 Correct 186 ms 6752 KB Output is correct
27 Correct 371 ms 82500 KB Output is correct
28 Correct 334 ms 42940 KB Output is correct
29 Correct 366 ms 77008 KB Output is correct
30 Correct 804 ms 193576 KB Output is correct
31 Correct 3 ms 468 KB Output is correct
32 Correct 690 ms 84636 KB Output is correct
33 Correct 812 ms 260088 KB Output is correct
34 Correct 355 ms 153928 KB Output is correct
35 Correct 600 ms 245908 KB Output is correct
36 Correct 410 ms 171696 KB Output is correct
37 Correct 89 ms 36928 KB Output is correct
38 Correct 171 ms 73540 KB Output is correct
39 Correct 540 ms 216200 KB Output is correct
40 Correct 511 ms 189784 KB Output is correct
41 Correct 100 ms 42124 KB Output is correct
42 Correct 297 ms 116492 KB Output is correct
43 Correct 862 ms 260128 KB Output is correct
44 Correct 355 ms 153812 KB Output is correct
45 Correct 644 ms 245928 KB Output is correct
46 Correct 420 ms 171712 KB Output is correct
47 Correct 101 ms 30564 KB Output is correct
48 Correct 168 ms 71620 KB Output is correct
49 Correct 416 ms 190112 KB Output is correct
50 Correct 653 ms 238616 KB Output is correct
51 Correct 628 ms 238464 KB Output is correct
52 Correct 546 ms 216196 KB Output is correct
53 Correct 482 ms 189828 KB Output is correct
54 Correct 105 ms 42108 KB Output is correct
55 Correct 286 ms 116516 KB Output is correct
56 Correct 806 ms 260136 KB Output is correct
57 Correct 374 ms 153768 KB Output is correct
58 Correct 587 ms 245864 KB Output is correct
59 Correct 419 ms 171652 KB Output is correct
60 Correct 76 ms 30564 KB Output is correct
61 Correct 170 ms 71580 KB Output is correct
62 Correct 409 ms 190056 KB Output is correct
63 Correct 649 ms 238588 KB Output is correct
64 Correct 597 ms 238544 KB Output is correct
65 Correct 681 ms 153216 KB Output is correct
66 Correct 1210 ms 262900 KB Output is correct
67 Correct 1135 ms 258692 KB Output is correct
68 Correct 743 ms 196712 KB Output is correct
69 Correct 924 ms 189992 KB Output is correct
70 Correct 66 ms 4936 KB Output is correct
71 Correct 1105 ms 262824 KB Output is correct
72 Correct 1130 ms 258580 KB Output is correct
73 Correct 824 ms 196820 KB Output is correct
74 Correct 800 ms 246664 KB Output is correct
75 Correct 820 ms 262932 KB Output is correct
76 Correct 764 ms 258584 KB Output is correct
77 Correct 575 ms 196912 KB Output is correct
78 Correct 787 ms 192544 KB Output is correct
79 Correct 1426 ms 219724 KB Output is correct
80 Correct 1444 ms 193336 KB Output is correct
81 Correct 445 ms 45560 KB Output is correct
82 Correct 633 ms 120028 KB Output is correct
83 Correct 1059 ms 263688 KB Output is correct
84 Correct 486 ms 157472 KB Output is correct
85 Correct 728 ms 249440 KB Output is correct
86 Correct 527 ms 175164 KB Output is correct
87 Correct 161 ms 33968 KB Output is correct
88 Correct 228 ms 75068 KB Output is correct
89 Correct 455 ms 193532 KB Output is correct
90 Correct 944 ms 242128 KB Output is correct
91 Correct 1035 ms 242156 KB Output is correct