oj.uz

Submission #1028442

# Submission time Handle Problem Language Result Execution time Memory
1028442 2024-07-19T21:12:09 Z _8_8_ Land of the Rainbow Gold (APIO17_rainbow) C++17
35 / 100
 3000 ms 506900 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 - _bf + 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 34 ms 348 KB Output is correct
2 Correct 118 ms 852 KB Output is correct
3 Correct 74 ms 628 KB Output is correct
4 Correct 97 ms 604 KB Output is correct
5 Correct 182 ms 860 KB Output is correct
6 Correct 1 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 0 ms 348 KB Output is correct
11 Correct 142 ms 700 KB Output is correct
12 Correct 287 ms 856 KB Output is correct
13 Correct 294 ms 856 KB Output is correct
14 Correct 523 ms 1228 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 3042 ms 67348 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 1028 ms 438044 KB Output is correct
3 Correct 905 ms 345884 KB Output is correct
4 Correct 943 ms 384788 KB Output is correct
5 Correct 568 ms 330768 KB Output is correct
6 Correct 968 ms 314728 KB Output is correct
7 Correct 1549 ms 349200 KB Output is correct
8 Correct 124 ms 33480 KB Output is correct
9 Correct 113 ms 31692 KB Output is correct
10 Correct 180 ms 136072 KB Output is correct
11 Correct 319 ms 162152 KB Output is correct
12 Correct 628 ms 407984 KB Output is correct
13 Correct 568 ms 317652 KB Output is correct
14 Correct 665 ms 361088 KB Output is correct
15 Correct 449 ms 324628 KB Output is correct
16 Correct 772 ms 301336 KB Output is correct
17 Correct 829 ms 304848 KB Output is correct
18 Correct 1126 ms 336804 KB Output is correct
19 Correct 1147 ms 410136 KB Output is correct
20 Correct 954 ms 398076 KB Output is correct
21 Correct 311 ms 50364 KB Output is correct
22 Correct 270 ms 46792 KB Output is correct
23 Correct 498 ms 159512 KB Output is correct
24 Correct 696 ms 195484 KB Output is correct
25 Correct 1836 ms 506900 KB Output is correct
26 Correct 1615 ms 414568 KB Output is correct
27 Correct 2056 ms 459992 KB Output is correct
28 Correct 1611 ms 420296 KB Output is correct
29 Correct 1608 ms 354148 KB Output is correct
30 Correct 1700 ms 366100 KB Output is correct
31 Correct 1755 ms 387996 KB Output is correct
32 Correct 1805 ms 460628 KB Output is correct
33 Correct 1775 ms 460752 KB Output is correct

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 348 KB Output is correct
2 Correct 118 ms 852 KB Output is correct
3 Correct 74 ms 628 KB Output is correct
4 Correct 97 ms 604 KB Output is correct
5 Correct 182 ms 860 KB Output is correct
6 Correct 1 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 0 ms 348 KB Output is correct
11 Correct 142 ms 700 KB Output is correct
12 Correct 287 ms 856 KB Output is correct
13 Correct 294 ms 856 KB Output is correct
14 Correct 523 ms 1228 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 3032 ms 21556 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 348 KB Output is correct
2 Correct 118 ms 852 KB Output is correct
3 Correct 74 ms 628 KB Output is correct
4 Correct 97 ms 604 KB Output is correct
5 Correct 182 ms 860 KB Output is correct
6 Correct 1 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 0 ms 348 KB Output is correct
11 Correct 142 ms 700 KB Output is correct
12 Correct 287 ms 856 KB Output is correct
13 Correct 294 ms 856 KB Output is correct
14 Correct 523 ms 1228 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 3032 ms 21556 KB Time limit exceeded
19 Halted 0 ms 0 KB -