oj.uz

Submission #1028420

# Submission time Handle Problem Language Result Execution time Memory
1028420 2024-07-19T20:02:44 Z _8_8_ Land of the Rainbow Gold (APIO17_rainbow) C++17
35 / 100
 3000 ms 210708 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;
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});
    }
    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);
    for(auto [x,y]:pts){
        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 V = 0,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;
    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})){
            bf++;
        }
        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()){
                V++;
                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;
    }
    return  -val-(br-ar+3)*2-(bc-ac+1)*2 + E - bf + 1+ok;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 344 KB Output is correct
2 Correct 133 ms 604 KB Output is correct
3 Correct 85 ms 348 KB Output is correct
4 Correct 107 ms 348 KB Output is correct
5 Correct 200 ms 724 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 169 ms 576 KB Output is correct
12 Correct 283 ms 600 KB Output is correct
13 Correct 344 ms 848 KB Output is correct
14 Correct 557 ms 856 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 344 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 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Execution timed out 3038 ms 55868 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 745 ms 141636 KB Output is correct
3 Correct 616 ms 118804 KB Output is correct
4 Correct 596 ms 123672 KB Output is correct
5 Correct 325 ms 97680 KB Output is correct
6 Correct 881 ms 125580 KB Output is correct
7 Correct 1458 ms 154648 KB Output is correct
8 Correct 66 ms 11204 KB Output is correct
9 Correct 56 ms 9408 KB Output is correct
10 Correct 58 ms 38088 KB Output is correct
11 Correct 138 ms 44908 KB Output is correct
12 Correct 346 ms 111976 KB Output is correct
13 Correct 232 ms 90456 KB Output is correct
14 Correct 324 ms 100148 KB Output is correct
15 Correct 230 ms 91160 KB Output is correct
16 Correct 743 ms 113428 KB Output is correct
17 Correct 731 ms 110580 KB Output is correct
18 Correct 1008 ms 130072 KB Output is correct
19 Correct 1008 ms 148508 KB Output is correct
20 Correct 738 ms 136472 KB Output is correct
21 Correct 323 ms 28096 KB Output is correct
22 Correct 225 ms 24512 KB Output is correct
23 Correct 378 ms 61508 KB Output is correct
24 Correct 558 ms 78288 KB Output is correct
25 Correct 1703 ms 210708 KB Output is correct
26 Correct 1653 ms 187672 KB Output is correct
27 Correct 1723 ms 199080 KB Output is correct
28 Correct 1648 ms 187052 KB Output is correct
29 Correct 1611 ms 166224 KB Output is correct
30 Correct 1691 ms 171688 KB Output is correct
31 Correct 1730 ms 180868 KB Output is correct
32 Correct 1771 ms 199224 KB Output is correct
33 Correct 1711 ms 199188 KB Output is correct

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 344 KB Output is correct
2 Correct 133 ms 604 KB Output is correct
3 Correct 85 ms 348 KB Output is correct
4 Correct 107 ms 348 KB Output is correct
5 Correct 200 ms 724 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 169 ms 576 KB Output is correct
12 Correct 283 ms 600 KB Output is correct
13 Correct 344 ms 848 KB Output is correct
14 Correct 557 ms 856 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Execution timed out 3025 ms 9384 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 344 KB Output is correct
2 Correct 133 ms 604 KB Output is correct
3 Correct 85 ms 348 KB Output is correct
4 Correct 107 ms 348 KB Output is correct
5 Correct 200 ms 724 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 169 ms 576 KB Output is correct
12 Correct 283 ms 600 KB Output is correct
13 Correct 344 ms 848 KB Output is correct
14 Correct 557 ms 856 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Execution timed out 3025 ms 9384 KB Time limit exceeded
19 Halted 0 ms 0 KB -