oj.uz

Submission #683431

# Submission time Handle Problem Language Result Execution time Memory
683431 2023-01-18T11:29:20 Z fatemetmhr Land of the Rainbow Gold (APIO17_rainbow) C++17
100 / 100
 898 ms 194276 KB 
// ~ Be Name Khoda ~

#include "rainbow.h"
#include<bits/stdc++.h>
//#pragma GCC optimize ("Ofast")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,O3")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  2e5   + 10;
const int maxnt =  8e5   + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const ll  inf   =  1e18;

struct segment_tree{

    vector <int> ini[maxn5], av[maxnt];

    void build(int l, int r, int v){
        if(r - l == 1){
            sort(all(ini[l]));
            for(auto u : ini[l])
                av[v].pb(u);
            return;
        }
        int mid = (l + r) >> 1;
        build(l, mid, v * 2);
        build(mid, r, v * 2 + 1);
        int pt1 = 0, pt2 = 0;
        while(pt1 < av[v * 2].size() || pt2 < av[v * 2 + 1].size()){
            if(pt1 < av[v * 2].size() && (pt2 == av[v * 2 + 1].size() || av[v * 2][pt1] < av[v * 2 + 1][pt2]))
                av[v].pb(av[v * 2][pt1++]);
            else
                av[v].pb(av[v * 2 + 1][pt2++]);
        }
    }

    int get(int l, int r, int lq, int rq, int lq2, int rq2, int v){
        if(rq <= l || r <= lq || lq2 >= rq2)
            return 0;
        if(lq <= l && r <= rq){
            int pl = lower_bound(all(av[v]), lq2) - av[v].begin();
            int pr = lower_bound(all(av[v]), rq2) - av[v].begin() - 1;
            //cout << "asking for " << l << ' ' << r << ' ' << lq << ' ' << rq << ' ' << lq2 << ' ' << rq2 << ' ' << pl << ' ' << pr << ' ' << av[v].size() << endl;
            return pr - pl + 1;
        }
        int mid = (l + r) >> 1;
        return get(l, mid, lq, rq, lq2, rq2, v * 2) + get(mid, r, lq, rq, lq2, rq2, v * 2 + 1);
    }

} segriv, segof, segam, segver;


int n, m;
vector <pair<int, int>> ver, riv;
vector <pair<pair<int, int>, pair<int, int>>> ed;


inline void add_edge(int x1, int yy1, int x2, int y2){
    if(mp(x1, yy1) > mp(x2, y2)){
        swap(x1, x2);
        swap(yy1, y2);
    }
    ver.pb({x1, yy1});
    ver.pb({x2, y2});
    ed.pb({{x1, yy1}, {x2, y2}});
}

void init(int R, int C, int sr, int sc, int M, char *S){
    n = R; m = C;
    n++; m++;
    sr--; sc--;
    riv.pb({sr, sc});
    add_edge(sr, sc, sr + 1, sc);
    add_edge(sr, sc, sr, sc + 1);
    add_edge(sr, sc + 1, sr + 1, sc + 1);
    add_edge(sr + 1, sc, sr + 1, sc + 1);
    for(int i = 0; i < M; i++){
        if(S[i] == 'N')
            sr--;
        if(S[i] == 'S')
            sr++;
        if(S[i] == 'E')
            sc++;
        if(S[i] == 'W')
            sc--;
        riv.pb({sr, sc});
        add_edge(sr, sc, sr + 1, sc);
        add_edge(sr, sc, sr, sc + 1);
        add_edge(sr, sc + 1, sr + 1, sc + 1);
        add_edge(sr + 1, sc, sr + 1, sc + 1);
    }
    sort(all(riv)); sort(all(ver)); sort(all(ed));
    riv.resize(unique(all(riv)) - riv.begin());
    ver.resize(unique(all(ver)) - ver.begin());
    ed.resize(unique(all(ed)) - ed.begin());
    for(auto [x, y] : riv){
        segriv.ini[x].pb(y);
        //cout << "river of " << x << ' ' << y << endl;
    }
    for(auto [x, y] : ver)
        segver.ini[x].pb(y);
    for(auto [p1, p2] : ed){
        if(p1.fi == p2.fi)
            segof.ini[p1.fi].pb(min(p1.se, p2.se));
        else
            segam.ini[min(p1.fi, p2.fi)].pb(p1.se);
    }
    segriv.build(0, n, 1);
    segver.build(0, n, 1);
    segof.build(0, n, 1);
    segam.build(0, n, 1);
}

int colour(int ax, int ay, int bx, int by){
    ax--; ay--; bx--; by--;
    ll nover = 4 + 2 * (bx - ax + by - ay), noed = 0, noriv = 0;
    if(ax < bx && ay < by)
        nover += segver.get(0, n, ax + 1, bx + 1, ay + 1, by + 1, 1);
    if(ax < bx)
        noed += segof.get(0, n, ax + 1, bx + 1, ay, by + 1, 1);
    if(ay < by)
        noed += segam.get(0, n, ax, bx + 1, ay + 1, by + 1, 1);
    noriv = segriv.get(0, n, ax, bx + 1, ay, by + 1, 1);
    if(noed == ed.size())
        noed++;
    noed += 2 * (bx - ax + by - ay + 2);
    //cout << "ok " << noed << ' ' << noriv << ' ' << nover << endl;
    return noed - nover + 1 - noriv;
}

/*
6 4 9 1
3 3
NWESSWEWS
1 2 5 3
2 3 2 3
3 2 4 4
5 3 6 4
*/

Compilation message

rainbow.cpp: In member function 'void segment_tree::build(int, int, int)':
rainbow.cpp:41:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         while(pt1 < av[v * 2].size() || pt2 < av[v * 2 + 1].size()){
      |               ~~~~^~~~~~~~~~~~~~~~~~
rainbow.cpp:41:45: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         while(pt1 < av[v * 2].size() || pt2 < av[v * 2 + 1].size()){
      |                                         ~~~~^~~~~~~~~~~~~~~~~~~~~~
rainbow.cpp:42:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |             if(pt1 < av[v * 2].size() && (pt2 == av[v * 2 + 1].size() || av[v * 2][pt1] < av[v * 2 + 1][pt2]))
      |                ~~~~^~~~~~~~~~~~~~~~~~
rainbow.cpp:42:47: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |             if(pt1 < av[v * 2].size() && (pt2 == av[v * 2 + 1].size() || av[v * 2][pt1] < av[v * 2 + 1][pt2]))
      |                                           ~~~~^~~~~~~~~~~~~~~~~~~~~~~
rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:136:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |     if(noed == ed.size())
      |        ~~~~~^~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 94304 KB Output is correct
2 Correct 52 ms 94664 KB Output is correct
3 Correct 45 ms 94260 KB Output is correct
4 Correct 46 ms 94376 KB Output is correct
5 Correct 48 ms 94792 KB Output is correct
6 Correct 43 ms 94184 KB Output is correct
7 Correct 44 ms 94224 KB Output is correct
8 Correct 47 ms 94164 KB Output is correct
9 Correct 45 ms 94160 KB Output is correct
10 Correct 43 ms 94256 KB Output is correct
11 Correct 46 ms 94412 KB Output is correct
12 Correct 47 ms 94612 KB Output is correct
13 Correct 47 ms 94796 KB Output is correct
14 Correct 49 ms 95176 KB Output is correct
15 Correct 43 ms 94212 KB Output is correct
16 Correct 44 ms 94168 KB Output is correct
17 Correct 43 ms 94156 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 94168 KB Output is correct
2 Correct 43 ms 94156 KB Output is correct
3 Correct 215 ms 108848 KB Output is correct
4 Correct 279 ms 118732 KB Output is correct
5 Correct 262 ms 118632 KB Output is correct
6 Correct 262 ms 116648 KB Output is correct
7 Correct 262 ms 115844 KB Output is correct
8 Correct 165 ms 109264 KB Output is correct
9 Correct 270 ms 118884 KB Output is correct
10 Correct 269 ms 118572 KB Output is correct
11 Correct 265 ms 116720 KB Output is correct
12 Correct 217 ms 117516 KB Output is correct
13 Correct 205 ms 118812 KB Output is correct
14 Correct 214 ms 118664 KB Output is correct
15 Correct 219 ms 116700 KB Output is correct
16 Correct 230 ms 112308 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 94212 KB Output is correct
2 Correct 213 ms 155492 KB Output is correct
3 Correct 293 ms 190404 KB Output is correct
4 Correct 255 ms 178656 KB Output is correct
5 Correct 219 ms 159720 KB Output is correct
6 Correct 177 ms 118092 KB Output is correct
7 Correct 194 ms 128232 KB Output is correct
8 Correct 167 ms 119672 KB Output is correct
9 Correct 215 ms 119928 KB Output is correct
10 Correct 118 ms 110612 KB Output is correct
11 Correct 192 ms 132096 KB Output is correct
12 Correct 202 ms 155612 KB Output is correct
13 Correct 292 ms 190432 KB Output is correct
14 Correct 252 ms 178784 KB Output is correct
15 Correct 219 ms 159892 KB Output is correct
16 Correct 175 ms 116136 KB Output is correct
17 Correct 195 ms 128556 KB Output is correct
18 Correct 230 ms 162084 KB Output is correct
19 Correct 240 ms 172364 KB Output is correct
20 Correct 243 ms 173304 KB Output is correct
21 Correct 166 ms 119604 KB Output is correct
22 Correct 183 ms 119936 KB Output is correct
23 Correct 119 ms 110612 KB Output is correct
24 Correct 193 ms 132140 KB Output is correct
25 Correct 200 ms 155576 KB Output is correct
26 Correct 292 ms 190532 KB Output is correct
27 Correct 253 ms 178816 KB Output is correct
28 Correct 216 ms 159880 KB Output is correct
29 Correct 175 ms 116136 KB Output is correct
30 Correct 204 ms 128552 KB Output is correct
31 Correct 227 ms 162092 KB Output is correct
32 Correct 239 ms 172328 KB Output is correct
33 Correct 267 ms 173328 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 94304 KB Output is correct
2 Correct 52 ms 94664 KB Output is correct
3 Correct 45 ms 94260 KB Output is correct
4 Correct 46 ms 94376 KB Output is correct
5 Correct 48 ms 94792 KB Output is correct
6 Correct 43 ms 94184 KB Output is correct
7 Correct 44 ms 94224 KB Output is correct
8 Correct 47 ms 94164 KB Output is correct
9 Correct 45 ms 94160 KB Output is correct
10 Correct 43 ms 94256 KB Output is correct
11 Correct 46 ms 94412 KB Output is correct
12 Correct 47 ms 94612 KB Output is correct
13 Correct 47 ms 94796 KB Output is correct
14 Correct 49 ms 95176 KB Output is correct
15 Correct 43 ms 94212 KB Output is correct
16 Correct 44 ms 94168 KB Output is correct
17 Correct 43 ms 94156 KB Output is correct
18 Correct 898 ms 129324 KB Output is correct
19 Correct 206 ms 98760 KB Output is correct
20 Correct 179 ms 97832 KB Output is correct
21 Correct 201 ms 97972 KB Output is correct
22 Correct 199 ms 98380 KB Output is correct
23 Correct 180 ms 98504 KB Output is correct
24 Correct 237 ms 98296 KB Output is correct
25 Correct 219 ms 98344 KB Output is correct
26 Correct 225 ms 98724 KB Output is correct
27 Correct 463 ms 126072 KB Output is correct
28 Correct 411 ms 118236 KB Output is correct
29 Correct 468 ms 124364 KB Output is correct
30 Correct 691 ms 145928 KB Output is correct
31 Correct 46 ms 94348 KB Output is correct
32 Correct 668 ms 126096 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 94304 KB Output is correct
2 Correct 52 ms 94664 KB Output is correct
3 Correct 45 ms 94260 KB Output is correct
4 Correct 46 ms 94376 KB Output is correct
5 Correct 48 ms 94792 KB Output is correct
6 Correct 43 ms 94184 KB Output is correct
7 Correct 44 ms 94224 KB Output is correct
8 Correct 47 ms 94164 KB Output is correct
9 Correct 45 ms 94160 KB Output is correct
10 Correct 43 ms 94256 KB Output is correct
11 Correct 46 ms 94412 KB Output is correct
12 Correct 47 ms 94612 KB Output is correct
13 Correct 47 ms 94796 KB Output is correct
14 Correct 49 ms 95176 KB Output is correct
15 Correct 43 ms 94212 KB Output is correct
16 Correct 44 ms 94168 KB Output is correct
17 Correct 43 ms 94156 KB Output is correct
18 Correct 898 ms 129324 KB Output is correct
19 Correct 206 ms 98760 KB Output is correct
20 Correct 179 ms 97832 KB Output is correct
21 Correct 201 ms 97972 KB Output is correct
22 Correct 199 ms 98380 KB Output is correct
23 Correct 180 ms 98504 KB Output is correct
24 Correct 237 ms 98296 KB Output is correct
25 Correct 219 ms 98344 KB Output is correct
26 Correct 225 ms 98724 KB Output is correct
27 Correct 463 ms 126072 KB Output is correct
28 Correct 411 ms 118236 KB Output is correct
29 Correct 468 ms 124364 KB Output is correct
30 Correct 691 ms 145928 KB Output is correct
31 Correct 46 ms 94348 KB Output is correct
32 Correct 668 ms 126096 KB Output is correct
33 Correct 213 ms 155492 KB Output is correct
34 Correct 293 ms 190404 KB Output is correct
35 Correct 255 ms 178656 KB Output is correct
36 Correct 219 ms 159720 KB Output is correct
37 Correct 177 ms 118092 KB Output is correct
38 Correct 194 ms 128232 KB Output is correct
39 Correct 167 ms 119672 KB Output is correct
40 Correct 215 ms 119928 KB Output is correct
41 Correct 118 ms 110612 KB Output is correct
42 Correct 192 ms 132096 KB Output is correct
43 Correct 202 ms 155612 KB Output is correct
44 Correct 292 ms 190432 KB Output is correct
45 Correct 252 ms 178784 KB Output is correct
46 Correct 219 ms 159892 KB Output is correct
47 Correct 175 ms 116136 KB Output is correct
48 Correct 195 ms 128556 KB Output is correct
49 Correct 230 ms 162084 KB Output is correct
50 Correct 240 ms 172364 KB Output is correct
51 Correct 243 ms 173304 KB Output is correct
52 Correct 166 ms 119604 KB Output is correct
53 Correct 183 ms 119936 KB Output is correct
54 Correct 119 ms 110612 KB Output is correct
55 Correct 193 ms 132140 KB Output is correct
56 Correct 200 ms 155576 KB Output is correct
57 Correct 292 ms 190532 KB Output is correct
58 Correct 253 ms 178816 KB Output is correct
59 Correct 216 ms 159880 KB Output is correct
60 Correct 175 ms 116136 KB Output is correct
61 Correct 204 ms 128552 KB Output is correct
62 Correct 227 ms 162092 KB Output is correct
63 Correct 239 ms 172328 KB Output is correct
64 Correct 267 ms 173328 KB Output is correct
65 Correct 215 ms 108848 KB Output is correct
66 Correct 279 ms 118732 KB Output is correct
67 Correct 262 ms 118632 KB Output is correct
68 Correct 262 ms 116648 KB Output is correct
69 Correct 262 ms 115844 KB Output is correct
70 Correct 165 ms 109264 KB Output is correct
71 Correct 270 ms 118884 KB Output is correct
72 Correct 269 ms 118572 KB Output is correct
73 Correct 265 ms 116720 KB Output is correct
74 Correct 217 ms 117516 KB Output is correct
75 Correct 205 ms 118812 KB Output is correct
76 Correct 214 ms 118664 KB Output is correct
77 Correct 219 ms 116700 KB Output is correct
78 Correct 230 ms 112308 KB Output is correct
79 Correct 354 ms 123124 KB Output is correct
80 Correct 410 ms 123440 KB Output is correct
81 Correct 368 ms 113944 KB Output is correct
82 Correct 502 ms 135540 KB Output is correct
83 Correct 559 ms 159144 KB Output is correct
84 Correct 872 ms 194276 KB Output is correct
85 Correct 628 ms 182284 KB Output is correct
86 Correct 624 ms 163376 KB Output is correct
87 Correct 473 ms 119604 KB Output is correct
88 Correct 494 ms 132044 KB Output is correct
89 Correct 546 ms 165524 KB Output is correct
90 Correct 718 ms 175916 KB Output is correct
91 Correct 718 ms 176776 KB Output is correct