oj.uz

Submission #1028443

# Submission time Handle Problem Language Result Execution time Memory
1028443 2024-07-19T21:15:59 Z _8_8_ Land of the Rainbow Gold (APIO17_rainbow) C++17
35 / 100
 3000 ms 644124 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);
    }
}
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+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;
        // }
    }
    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 += 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;
}

Compilation message

rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:146:14: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
  146 |         auto [r,c] = xx;
      |              ^~~~~
rainbow.cpp:144:17: warning: unused variable 'tt' [-Wunused-variable]
  144 |     int _bf = 0,tt = 0;;
      |                 ^~
rainbow.cpp:155:9: warning: unused variable 'bord_sum' [-Wunused-variable]
  155 |     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 6 ms 600 KB Output is correct
2 Correct 16 ms 860 KB Output is correct
3 Correct 11 ms 720 KB Output is correct
4 Correct 12 ms 756 KB Output is correct
5 Correct 22 ms 1108 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 444 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 18 ms 768 KB Output is correct
12 Correct 28 ms 968 KB Output is correct
13 Correct 35 ms 1188 KB Output is correct
14 Correct 65 ms 1372 KB Output is correct
15 Correct 0 ms 344 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 3037 ms 46540 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 344 KB Output is correct
2 Correct 699 ms 609556 KB Output is correct
3 Correct 628 ms 471060 KB Output is correct
4 Correct 776 ms 535828 KB Output is correct
5 Correct 513 ms 476020 KB Output is correct
6 Correct 474 ms 408796 KB Output is correct
7 Correct 611 ms 432248 KB Output is correct
8 Correct 113 ms 42184 KB Output is correct
9 Correct 115 ms 42004 KB Output is correct
10 Correct 221 ms 200312 KB Output is correct
11 Correct 300 ms 237724 KB Output is correct
12 Correct 617 ms 597872 KB Output is correct
13 Correct 547 ms 464600 KB Output is correct
14 Correct 677 ms 529520 KB Output is correct
15 Correct 486 ms 476068 KB Output is correct
16 Correct 456 ms 400964 KB Output is correct
17 Correct 544 ms 409896 KB Output is correct
18 Correct 596 ms 439836 KB Output is correct
19 Correct 660 ms 549344 KB Output is correct
20 Correct 650 ms 543216 KB Output is correct
21 Correct 138 ms 50628 KB Output is correct
22 Correct 151 ms 49604 KB Output is correct
23 Correct 263 ms 209784 KB Output is correct
24 Correct 353 ms 252012 KB Output is correct
25 Correct 766 ms 644124 KB Output is correct
26 Correct 677 ms 505364 KB Output is correct
27 Correct 864 ms 573468 KB Output is correct
28 Correct 633 ms 518084 KB Output is correct
29 Correct 517 ms 427280 KB Output is correct
30 Correct 627 ms 440380 KB Output is correct
31 Correct 697 ms 465176 KB Output is correct
32 Correct 727 ms 574740 KB Output is correct
33 Correct 731 ms 574700 KB Output is correct

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 600 KB Output is correct
2 Correct 16 ms 860 KB Output is correct
3 Correct 11 ms 720 KB Output is correct
4 Correct 12 ms 756 KB Output is correct
5 Correct 22 ms 1108 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 444 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 18 ms 768 KB Output is correct
12 Correct 28 ms 968 KB Output is correct
13 Correct 35 ms 1188 KB Output is correct
14 Correct 65 ms 1372 KB Output is correct
15 Correct 0 ms 344 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 3068 ms 25520 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 600 KB Output is correct
2 Correct 16 ms 860 KB Output is correct
3 Correct 11 ms 720 KB Output is correct
4 Correct 12 ms 756 KB Output is correct
5 Correct 22 ms 1108 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 444 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 18 ms 768 KB Output is correct
12 Correct 28 ms 968 KB Output is correct
13 Correct 35 ms 1188 KB Output is correct
14 Correct 65 ms 1372 KB Output is correct
15 Correct 0 ms 344 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 3068 ms 25520 KB Time limit exceeded
19 Halted 0 ms 0 KB -