Submission #1028420

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028420		_8_8_	Land of the Rainbow Gold (APIO17_rainbow)	C++17	35 / 100	3038 ms	210708 KiB

rainbow

#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 / 11
• Subtask 2: 0 / 12
• Subtask 3: 24 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26