Submission #1028444

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028444		_8_8_	Land of the Rainbow Gold (APIO17_rainbow)	C++17	100 / 100	1577 ms	597852 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,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);
    }
}
int colour(int ar, int ac, int br, int bc) {
    int E = 0;
    int _bf = 0;
    int val =ver.get(ar,br,ac,bc,1,1,ver.n); 
    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;
}

• Subtask 1: 11 / 11
• Subtask 2: 12 / 12
• Subtask 3: 24 / 24
• Subtask 4: 27 / 27
• Subtask 5: 26 / 26