oj.uz

Submission #1028441

# Submission time Handle Problem Language Result Execution time Memory
1028441 2024-07-19T21:11:39 Z _8_8_ Land of the Rainbow Gold (APIO17_rainbow) C++17
35 / 100
 3000 ms 506988 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);
    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);
    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);
        }
        // cout << x << ' ' << y<<'\n';
        if(in.count({x,y-1})){
            ll.upd(x,y,1,1,1,ll.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 += 1;
        }
        if(k.count({r+1,c-1}) && !k.count({r+1,c}) && !k.count({r,c-1})){
            E += 1;
        }
        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});
                    }
                }
            }
        }
    }
    int val =ver.get(ar,br,ac,bc,1,1,ver.n); 
    int bord_sum =(br-ar+3)*2+(bc-ac+1)*2;
    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 += (ll.get(ar,br,ac+1,bc,1,1,ll.n) + uu.get(ar+1,br,ac,bc,1,1,uu.n)) + _;
    // E/=2;
    // cout << (ll.get(ar,br,ac+1,bc,1,1,ll.n) + uu.get(ar+1,br,ac,bc,1,1,uu.n)) << "x\n";
    return  -val+ E - tt + 1+ok;
}

Compilation message

rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:171:9: warning: unused variable 'bord_sum' [-Wunused-variable]
  171 |     int bord_sum =(br-ar+3)*2+(bc-ac+1)*2;
      |         ^~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 348 KB Output is correct
2 Correct 107 ms 860 KB Output is correct
3 Correct 68 ms 604 KB Output is correct
4 Correct 84 ms 600 KB Output is correct
5 Correct 169 ms 860 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 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 134 ms 728 KB Output is correct
12 Correct 241 ms 856 KB Output is correct
13 Correct 270 ms 860 KB Output is correct
14 Correct 475 ms 1328 KB Output is correct
15 Correct 1 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 3061 ms 67456 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 938 ms 438044 KB Output is correct
3 Correct 787 ms 345656 KB Output is correct
4 Correct 867 ms 384912 KB Output is correct
5 Correct 509 ms 330904 KB Output is correct
6 Correct 1026 ms 314668 KB Output is correct
7 Correct 1426 ms 349228 KB Output is correct
8 Correct 126 ms 33480 KB Output is correct
9 Correct 120 ms 31688 KB Output is correct
10 Correct 187 ms 135840 KB Output is correct
11 Correct 271 ms 162164 KB Output is correct
12 Correct 619 ms 408100 KB Output is correct
13 Correct 479 ms 317552 KB Output is correct
14 Correct 588 ms 360980 KB Output is correct
15 Correct 481 ms 324624 KB Output is correct
16 Correct 753 ms 301584 KB Output is correct
17 Correct 828 ms 304980 KB Output is correct
18 Correct 1128 ms 336656 KB Output is correct
19 Correct 1073 ms 410140 KB Output is correct
20 Correct 900 ms 398256 KB Output is correct
21 Correct 295 ms 50368 KB Output is correct
22 Correct 295 ms 46788 KB Output is correct
23 Correct 454 ms 159720 KB Output is correct
24 Correct 637 ms 195440 KB Output is correct
25 Correct 1844 ms 506988 KB Output is correct
26 Correct 1907 ms 414744 KB Output is correct
27 Correct 1892 ms 460060 KB Output is correct
28 Correct 1789 ms 420500 KB Output is correct
29 Correct 1724 ms 354232 KB Output is correct
30 Correct 1764 ms 366096 KB Output is correct
31 Correct 1937 ms 387836 KB Output is correct
32 Correct 1874 ms 460780 KB Output is correct
33 Correct 1742 ms 460752 KB Output is correct

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 348 KB Output is correct
2 Correct 107 ms 860 KB Output is correct
3 Correct 68 ms 604 KB Output is correct
4 Correct 84 ms 600 KB Output is correct
5 Correct 169 ms 860 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 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 134 ms 728 KB Output is correct
12 Correct 241 ms 856 KB Output is correct
13 Correct 270 ms 860 KB Output is correct
14 Correct 475 ms 1328 KB Output is correct
15 Correct 1 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 3040 ms 21800 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 348 KB Output is correct
2 Correct 107 ms 860 KB Output is correct
3 Correct 68 ms 604 KB Output is correct
4 Correct 84 ms 600 KB Output is correct
5 Correct 169 ms 860 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 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 134 ms 728 KB Output is correct
12 Correct 241 ms 856 KB Output is correct
13 Correct 270 ms 860 KB Output is correct
14 Correct 475 ms 1328 KB Output is correct
15 Correct 1 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 3040 ms 21800 KB Time limit exceeded
19 Halted 0 ms 0 KB -