oj.uz

Submission #1028444

# Submission time Handle Problem Language Result Execution time Memory
1028444 2024-07-19T21:16:48 Z _8_8_ Land of the Rainbow Gold (APIO17_rainbow) C++17
100 / 100
 1577 ms 597852 KB 
#include <bits/stdc++.h>
#include "rainbow.h"
 
using namespace std;
 
vector<pair<int,int>> pts;
struct segtr{
    vector<int> t;
    int n;
    void init(int s){
        n = s;
        t.assign((s + 1) * 4,0);
    }
    void upd(int pos,int val,int v,int tl,int tr){
        t[v] += val;
        if(tl == tr){
            return;
        }
        int tm = (tl + tr) >> 1;
        if(pos <= tm) upd(pos,val,v+v,tl,tm);
        else upd(pos,val,v+v+1,tm+1,tr);
    }
    int get(int l,int r,int v,int tl,int tr){
        if(l > r || tl >r || l > tr) return 0;
        if(tl >= l && tr <= r) return t[v];
        int tm = (tl + tr) >> 1;
        return get(l,r,v+v,tl,tm) + get(l,r,v+v+1,tm+1,tr);
    }
};

struct dd{
    vector<vector<int>> f,t;
    vector<segtr> b;
    int n;
    void build(int v,int tl,int tr){
        if(tl == tr){
            t[v] = f[tl];
            t[v].resize(unique(t[v].begin(),t[v].end()) - t[v].begin());
            // cerr << (int)t[v].size() << '\n';
            b[v].init((int)t[v].size());
        }else{
            int tm = (tl + tr) >> 1;
            build(v+v,tl,tm);
            build(v + v + 1,tm + 1,tr);
            t[v].resize((int)t[v+v].size() + (int)t[v +v + 1].size());
            merge(t[v + v].begin(),t[v + v].end(),t[v + v + 1].begin(),t[v + v + 1].end(),t[v].begin());
            t[v].resize(unique(t[v].begin(),t[v].end()) - t[v].begin());
            b[v].init((int)t[v].size());
        }
    }
    void init(int s,vector<vector<int>> _f){
        n = s;
        t.resize((n + 1) * 4);
        b.resize((n+1)*4);
        f = _f;
        build(1,1,n);
    }
    void upd(int x,int y,int val,int v,int tl,int tr){
        int it = lower_bound(t[v].begin(),t[v].end(),y)-t[v].begin()+1;
        b[v].upd(it,val,1,1,b[v].n);
        if(tl == tr) return;
        int tm = (tl + tr) >> 1;
        if(x <= tm) upd(x,y,val,v+v,tl,tm);
        else upd(x,y,val,v+v+1,tm+1,tr);
    }
    int get(int l,int r,int l1,int r1,int v,int tl,int tr){
        // return 0;
        if(l > r || tl > r || l > tr) return 0;
        if(tl >= l && tr <= r){
            int it = lower_bound(t[v].begin(),t[v].end(),l1)-t[v].begin()+1;
            int it1 = upper_bound(t[v].begin(),t[v].end(),r1)-t[v].begin();
            return b[v].get(it,it1,1,1,b[v].n);
        }
        int tm =(tl+tr)>>1;
        return get(l,r,l1,r1,v+v,tl,tm)+get(l,r,l1,r1,v+v+1,tm+1,tr);
    }
}ver,bf,uu,ll,d1,d2;
map<pair<int,int>,int>in;
void init(int R, int C, int sr, int sc, int M, char *S) {
    pts.push_back({sr,sc});
    vector<vector<int>> f(R+1);
    in[{sr,sc}]=1;
    for(int i = 0;i < M;i++){
        if(S[i] == 'N'){
            sr--;
        }else if(S[i] == 'S'){
            sr++;
        }else if(S[i] == 'W'){
            sc--;
        }else{
            sc++;
        }
        assert(sr <= R && sr >= 1);
        assert(sc <= C && sc >= 1);
        pts.push_back({sr,sc});
        in[{sr,sc}]=1;
    }
    sort(pts.begin(),pts.end());
    pts.resize(unique(pts.begin(),pts.end()) - pts.begin());
    for(auto [x,y]:pts){
        f[x].push_back(y);
    }
    ver.init(R,f);
    bf.init(R,f);
    uu.init(R,f);ll.init(R,f);
    d1.init(R,f);d2.init(R,f);
    for(auto [x,y]:pts){
        if(in.count({x+1,y})&&in.count({x,y+1})&&in.count({x+1,y+1})){
            bf.upd(x,y,1,1,1,bf.n);
        }
        if(in.count({x-1,y}))
        {
            uu.upd(x,y,1,1,1,uu.n);
        }
        if(in.count({x,y-1})){
            ll.upd(x,y,1,1,1,ll.n);
        }
        if(in.count({x+1,y+1}) && !in.count({x+1,y}) && !in.count({x,y+1})){
            d1.upd(x,y,1,1,1,uu.n);
        }
        if(in.count({x+1,y-1}) && !in.count({x+1,y}) && !in.count({x,y-1})){
            d2.upd(x,y,1,1,1,uu.n);
        }
        ver.upd(x,y,1,1,1,ver.n);
    }
}
int colour(int ar, int ac, int br, int bc) {
    int E = 0;
    int _bf = 0;
    int val =ver.get(ar,br,ac,bc,1,1,ver.n); 
    bool ok = false;
    int _ = ver.get(ar,ar,ac,bc,1,1,ver.n)+ver.get(ar,br,bc,bc,1,1,ver.n)+ver.get(ar,br,ac,ac,1,1,ver.n)+ver.get(br,br,ac,bc,1,1,ver.n);
    if(val > 0 && _==0){
        ok=1;
    }   
    _bf = (in.count({ar,ac})) + (in.count({ar,bc}))+(in.count({br,ac})) + (in.count({br,bc})) + bf.get(ar,br-1,ac,bc-1,1,1,bf.n);
    _bf += ll.get(ar,ar,ac+1,bc,1,1,ll.n)+ll.get(br,br,ac+1,bc,1,1,ll.n);
    _bf += uu.get(ar+1,br,ac,ac,1,1,uu.n)+uu.get(ar+1,br,bc,bc,1,1,uu.n);
    E += d1.get(ar,br-1,ac,bc-1,1,1,d1.n);
    E += d2.get(ar,br-1,ac+1,bc,1,1,d2.n);
    E += (ll.get(ar,br,ac+1,bc,1,1,ll.n) + uu.get(ar+1,br,ac,bc,1,1,uu.n)) + _;
    return  -val+ E - _bf + 1+ok;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 4 ms 860 KB Output is correct
3 Correct 3 ms 676 KB Output is correct
4 Correct 3 ms 704 KB Output is correct
5 Correct 5 ms 860 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 3 ms 732 KB Output is correct
12 Correct 5 ms 856 KB Output is correct
13 Correct 6 ms 1092 KB Output is correct
14 Correct 7 ms 1116 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 255 ms 23716 KB Output is correct
4 Correct 324 ms 37576 KB Output is correct
5 Correct 328 ms 36700 KB Output is correct
6 Correct 244 ms 29368 KB Output is correct
7 Correct 326 ms 27092 KB Output is correct
8 Correct 55 ms 4808 KB Output is correct
9 Correct 344 ms 37460 KB Output is correct
10 Correct 343 ms 36796 KB Output is correct
11 Correct 265 ms 29444 KB Output is correct
12 Correct 157 ms 35480 KB Output is correct
13 Correct 141 ms 37384 KB Output is correct
14 Correct 156 ms 36524 KB Output is correct
15 Correct 175 ms 29384 KB Output is correct
16 Correct 218 ms 27676 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 611 ms 597660 KB Output is correct
3 Correct 501 ms 464632 KB Output is correct
4 Correct 644 ms 529628 KB Output is correct
5 Correct 451 ms 475820 KB Output is correct
6 Correct 357 ms 387172 KB Output is correct
7 Correct 439 ms 397168 KB Output is correct
8 Correct 100 ms 40640 KB Output is correct
9 Correct 108 ms 41412 KB Output is correct
10 Correct 201 ms 200144 KB Output is correct
11 Correct 264 ms 237700 KB Output is correct
12 Correct 621 ms 597616 KB Output is correct
13 Correct 534 ms 464708 KB Output is correct
14 Correct 641 ms 529536 KB Output is correct
15 Correct 494 ms 475756 KB Output is correct
16 Correct 352 ms 385428 KB Output is correct
17 Correct 464 ms 396900 KB Output is correct
18 Correct 512 ms 419180 KB Output is correct
19 Correct 589 ms 531300 KB Output is correct
20 Correct 585 ms 531312 KB Output is correct
21 Correct 107 ms 40656 KB Output is correct
22 Correct 117 ms 41616 KB Output is correct
23 Correct 224 ms 200344 KB Output is correct
24 Correct 292 ms 237728 KB Output is correct
25 Correct 656 ms 597636 KB Output is correct
26 Correct 628 ms 464512 KB Output is correct
27 Correct 706 ms 529464 KB Output is correct
28 Correct 503 ms 475756 KB Output is correct
29 Correct 391 ms 385392 KB Output is correct
30 Correct 454 ms 396916 KB Output is correct
31 Correct 538 ms 418928 KB Output is correct
32 Correct 570 ms 531316 KB Output is correct
33 Correct 555 ms 531060 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 4 ms 860 KB Output is correct
3 Correct 3 ms 676 KB Output is correct
4 Correct 3 ms 704 KB Output is correct
5 Correct 5 ms 860 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 3 ms 732 KB Output is correct
12 Correct 5 ms 856 KB Output is correct
13 Correct 6 ms 1092 KB Output is correct
14 Correct 7 ms 1116 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 807 ms 26048 KB Output is correct
19 Correct 265 ms 5972 KB Output is correct
20 Correct 269 ms 4180 KB Output is correct
21 Correct 273 ms 4752 KB Output is correct
22 Correct 275 ms 5460 KB Output is correct
23 Correct 244 ms 6028 KB Output is correct
24 Correct 287 ms 4412 KB Output is correct
25 Correct 329 ms 4948 KB Output is correct
26 Correct 294 ms 5460 KB Output is correct
27 Correct 567 ms 24388 KB Output is correct
28 Correct 516 ms 17092 KB Output is correct
29 Correct 623 ms 25932 KB Output is correct
30 Correct 869 ms 48280 KB Output is correct
31 Correct 4 ms 348 KB Output is correct
32 Correct 853 ms 26232 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 4 ms 860 KB Output is correct
3 Correct 3 ms 676 KB Output is correct
4 Correct 3 ms 704 KB Output is correct
5 Correct 5 ms 860 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 3 ms 732 KB Output is correct
12 Correct 5 ms 856 KB Output is correct
13 Correct 6 ms 1092 KB Output is correct
14 Correct 7 ms 1116 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 807 ms 26048 KB Output is correct
19 Correct 265 ms 5972 KB Output is correct
20 Correct 269 ms 4180 KB Output is correct
21 Correct 273 ms 4752 KB Output is correct
22 Correct 275 ms 5460 KB Output is correct
23 Correct 244 ms 6028 KB Output is correct
24 Correct 287 ms 4412 KB Output is correct
25 Correct 329 ms 4948 KB Output is correct
26 Correct 294 ms 5460 KB Output is correct
27 Correct 567 ms 24388 KB Output is correct
28 Correct 516 ms 17092 KB Output is correct
29 Correct 623 ms 25932 KB Output is correct
30 Correct 869 ms 48280 KB Output is correct
31 Correct 4 ms 348 KB Output is correct
32 Correct 853 ms 26232 KB Output is correct
33 Correct 611 ms 597660 KB Output is correct
34 Correct 501 ms 464632 KB Output is correct
35 Correct 644 ms 529628 KB Output is correct
36 Correct 451 ms 475820 KB Output is correct
37 Correct 357 ms 387172 KB Output is correct
38 Correct 439 ms 397168 KB Output is correct
39 Correct 100 ms 40640 KB Output is correct
40 Correct 108 ms 41412 KB Output is correct
41 Correct 201 ms 200144 KB Output is correct
42 Correct 264 ms 237700 KB Output is correct
43 Correct 621 ms 597616 KB Output is correct
44 Correct 534 ms 464708 KB Output is correct
45 Correct 641 ms 529536 KB Output is correct
46 Correct 494 ms 475756 KB Output is correct
47 Correct 352 ms 385428 KB Output is correct
48 Correct 464 ms 396900 KB Output is correct
49 Correct 512 ms 419180 KB Output is correct
50 Correct 589 ms 531300 KB Output is correct
51 Correct 585 ms 531312 KB Output is correct
52 Correct 107 ms 40656 KB Output is correct
53 Correct 117 ms 41616 KB Output is correct
54 Correct 224 ms 200344 KB Output is correct
55 Correct 292 ms 237728 KB Output is correct
56 Correct 656 ms 597636 KB Output is correct
57 Correct 628 ms 464512 KB Output is correct
58 Correct 706 ms 529464 KB Output is correct
59 Correct 503 ms 475756 KB Output is correct
60 Correct 391 ms 385392 KB Output is correct
61 Correct 454 ms 396916 KB Output is correct
62 Correct 538 ms 418928 KB Output is correct
63 Correct 570 ms 531316 KB Output is correct
64 Correct 555 ms 531060 KB Output is correct
65 Correct 255 ms 23716 KB Output is correct
66 Correct 324 ms 37576 KB Output is correct
67 Correct 328 ms 36700 KB Output is correct
68 Correct 244 ms 29368 KB Output is correct
69 Correct 326 ms 27092 KB Output is correct
70 Correct 55 ms 4808 KB Output is correct
71 Correct 344 ms 37460 KB Output is correct
72 Correct 343 ms 36796 KB Output is correct
73 Correct 265 ms 29444 KB Output is correct
74 Correct 157 ms 35480 KB Output is correct
75 Correct 141 ms 37384 KB Output is correct
76 Correct 156 ms 36524 KB Output is correct
77 Correct 175 ms 29384 KB Output is correct
78 Correct 218 ms 27676 KB Output is correct
79 Correct 622 ms 44228 KB Output is correct
80 Correct 708 ms 45000 KB Output is correct
81 Correct 743 ms 201324 KB Output is correct
82 Correct 835 ms 238956 KB Output is correct
83 Correct 1426 ms 597852 KB Output is correct
84 Correct 1522 ms 464808 KB Output is correct
85 Correct 1559 ms 529888 KB Output is correct
86 Correct 1549 ms 476040 KB Output is correct
87 Correct 1105 ms 385652 KB Output is correct
88 Correct 1169 ms 397184 KB Output is correct
89 Correct 1319 ms 419264 KB Output is correct
90 Correct 1577 ms 531460 KB Output is correct
91 Correct 1471 ms 531408 KB Output is correct