oj.uz

Submission #1028429

# Submission time Handle Problem Language Result Execution time Memory
1028429 2024-07-19T20:34:19 Z _8_8_ Land of the Rainbow Gold (APIO17_rainbow) C++17
35 / 100
 3000 ms 507048 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;
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);
    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);
    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,bf.n);
        }
        if(in.count({x,y-1})){
            ll.upd(x,y,1,1,1,bf.n);
        }
        ver.upd(x,y,1,1,1,ver.n);
    }
}
const int dx[] = {1,0,-1,0},dy[] = {0,1,0,-1};
map<pair<int,int>,bool> k,vis;
int colour(int ar, int ac, int br, int bc) {
    k.clear();
    vis.clear();
    int E = 0;
    for(auto [r,c]:pts){
        if(r >= ar && r <= br && c >= ac && c <= bc){
            k[{r,c}] = 1;
        }
    }
    for(int i = ar - 1;i <= br + 1;i++){
        k[{i,ac-1}] = k[{i,bc+1}] = 1;
    }
    for(int i = ac - 1;i <= bc + 1;i++){
        k[{ar-1,i}] = k[{br+1,i}] = 1;
    }
    int _bf = 0,tt = 0;;
    for(auto [xx,_y]:k){
        auto [r,c] = xx;
        if(k.count({r + 1,c}) && k.count({r,c + 1}) && k.count({r + 1,c + 1})){
            tt++;
        }
        if(k.count({r+1,c+1}) && !k.count({r+1,c}) && !k.count({r,c+1})){
            E += 2;
        }
        if(k.count({r+1,c-1}) && !k.count({r+1,c}) && !k.count({r,c-1})){
            E += 2;
        }
        if(!vis.count({r,c})){
            queue<pair<int,int>> q;
            q.push({r,c});
            vis[{r,c}]=1;
            while(!q.empty()){
                auto [x,y] = q.front();q.pop();
                // cout << x << ' ' << y << '\n';
                for(int i = 0;i < 4;i++){
                    int _x = x + dx[i],_y = y + dy[i];
                    if(k.count({_x,_y})){
                        E++;
                    }
                    if(k.count({_x,_y}) && !vis.count({_x,_y})){
                        vis[{_x,_y}]=1;
                        q.push({_x,_y});
                    }
                }
            }
        }
    }
    assert(E%2==0);
    E /= 2; 
    int val =ver.get(ar,br,ac,bc,1,1,ver.n); 
    bool ok = false;
    if(val > 0 && ver.get(ar,ar,ac,bc,1,1,ver.n)==0 && ver.get(ar,br,bc,bc,1,1,ver.n)==0
        && ver.get(br,br,ac,bc,1,1,ver.n)==0 && ver.get(ar,br,ac,ac,1,1,ver.n)==0
    ){
        ok=1;
    }   
    _bf = (in.count({ar,ac})) + (in.count({ar,bc}))+(in.count({br,ac})) + (in.count({br,bc}));
    _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);
    // cout << _bf << ' '  <<tt<<'\n';
    return  -val-(br-ar+3)*2-(bc-ac+1)*2 + E - tt + 1+ok;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 548 KB Output is correct
2 Correct 135 ms 856 KB Output is correct
3 Correct 79 ms 600 KB Output is correct
4 Correct 92 ms 604 KB Output is correct
5 Correct 219 ms 1012 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 444 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 168 ms 720 KB Output is correct
12 Correct 302 ms 888 KB Output is correct
13 Correct 336 ms 1056 KB Output is correct
14 Correct 562 ms 1112 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
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 Execution timed out 3080 ms 67492 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1012 ms 438044 KB Output is correct
3 Correct 907 ms 345844 KB Output is correct
4 Correct 950 ms 384912 KB Output is correct
5 Correct 593 ms 331020 KB Output is correct
6 Correct 1177 ms 314688 KB Output is correct
7 Correct 1727 ms 349200 KB Output is correct
8 Correct 130 ms 33472 KB Output is correct
9 Correct 112 ms 31684 KB Output is correct
10 Correct 168 ms 135844 KB Output is correct
11 Correct 321 ms 162024 KB Output is correct
12 Correct 636 ms 408084 KB Output is correct
13 Correct 542 ms 317460 KB Output is correct
14 Correct 653 ms 360984 KB Output is correct
15 Correct 506 ms 324568 KB Output is correct
16 Correct 977 ms 301332 KB Output is correct
17 Correct 992 ms 304992 KB Output is correct
18 Correct 1357 ms 336636 KB Output is correct
19 Correct 1299 ms 410148 KB Output is correct
20 Correct 968 ms 398188 KB Output is correct
21 Correct 337 ms 50372 KB Output is correct
22 Correct 308 ms 47040 KB Output is correct
23 Correct 597 ms 159516 KB Output is correct
24 Correct 732 ms 195444 KB Output is correct
25 Correct 2129 ms 507048 KB Output is correct
26 Correct 2110 ms 414580 KB Output is correct
27 Correct 2069 ms 460060 KB Output is correct
28 Correct 1884 ms 420372 KB Output is correct
29 Correct 1824 ms 354260 KB Output is correct
30 Correct 1951 ms 366108 KB Output is correct
31 Correct 1876 ms 387852 KB Output is correct
32 Correct 2074 ms 460712 KB Output is correct
33 Correct 1967 ms 460820 KB Output is correct

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 548 KB Output is correct
2 Correct 135 ms 856 KB Output is correct
3 Correct 79 ms 600 KB Output is correct
4 Correct 92 ms 604 KB Output is correct
5 Correct 219 ms 1012 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 444 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 168 ms 720 KB Output is correct
12 Correct 302 ms 888 KB Output is correct
13 Correct 336 ms 1056 KB Output is correct
14 Correct 562 ms 1112 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 Execution timed out 3087 ms 21756 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 548 KB Output is correct
2 Correct 135 ms 856 KB Output is correct
3 Correct 79 ms 600 KB Output is correct
4 Correct 92 ms 604 KB Output is correct
5 Correct 219 ms 1012 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 444 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 168 ms 720 KB Output is correct
12 Correct 302 ms 888 KB Output is correct
13 Correct 336 ms 1056 KB Output is correct
14 Correct 562 ms 1112 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 Execution timed out 3087 ms 21756 KB Time limit exceeded
19 Halted 0 ms 0 KB -