제출 #563328

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
563328		leaked	Land of the Rainbow Gold (APIO17_rainbow)	C++17	0 / 100	273 ms	85568 KiB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>

#define f first
#define s second
#define m_p make_pair
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
typedef long double ld;
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}

const int tx[4]={1,-1,0,0};
const int ty[4]={0,0,1,-1};
const char wow[4]={'S','N','E','W'};
const int N=2e5+3;

struct fenwick{
    vec<int> a;
    vec<int> fen;
    void build(){
        sort(all(a));
        a.erase(unique(all(a)),a.end());
        fen.assign(sz(a)+1,0);
    }
    void upd(int i,int x){
        int id=i;
        i=lower_bound(all(a),i)-a.begin();
        assert(id==a[i]);
        ++i;
        while(i<sz(fen)){
            fen[i]+=x;
            i+=i&-i;
        }
    }
    int get(int i){
        i=upper_bound(all(a),i)-a.begin()-1;
        ++i;
        int ans=0;
        while(i>0){
            ans+=fen[i];
            i-=i&-i;
        }
//        cout<<"LOS "<<ans<<endl;
        return ans;
    }
    int get(int l,int r){
        return get(r)-get(l-1);
    }
};
struct _2d{
    fenwick fnw[N];
    vec<pii> w;
    void add(int i,int x){
        w.pb({i,x});
        ++i;
        while(i<N){
            fnw[i].a.pb(x);
            i+=i&-i;
        }
    }
    void upd(int i,int j,int x){
        ++i;
        while(i<N){
            fnw[i].upd(j,x);
            i+=i&-i;
        }
    }
    void build(){
        for(int i=0;i<N;i++)
            fnw[i].build();
        for(auto &z : w)
            upd(z.f,z.s,1);
    }
    int get(int i,int l,int r){
        ++i;
        int ans=0;
        while(i>0){
            ans+=fnw[i].get(l,r);
            i-=i&-i;
        }
        return ans;
    }
    int get(int l1,int r1,int l,int r){
        if(l1>r1 || l>r)
            return 0;
        return get(r1,l,r)-get(l1-1,l,r);
    }

}x,y,kv,pt;
void init(int n,int m, int sr, int sc, int l, char *S) {
    vec<pii> here;
    here.pb({sr,sc});
    for(int i=0;i<l;i++){
        int j=find(wow,wow+4,S[i])-wow;
        sr+=tx[j];sc+=ty[j];
        here.pb({sr,sc});
//        cout<<"W "<<sr<<' '<<sc<<endl;
    }
    sort(all(here));here.erase(unique(all(here)),here.end());
    vec<pii> w1,w2;
    auto check=[&](pii p){
        return binary_search(all(here),p);
    };
    for(auto &z : here){
//        cout<<"P "<<z.f<<' '<<z.s<<endl;
        if(check(m_p(z.f-1,z.s))){
            x.add(z.f,z.s);
        }
        if(check(m_p(z.f,z.s-1))){
            y.add(z.f,z.s);
        }
        pt.add(z.f,z.s);
        if(check(m_p(z.f,z.s-1)) && check(m_p(z.f-1,z.s-1)) && check(m_p(z.f-1,z.s))){
            kv.add(z.f,z.s);
        }
    }
    kv.build();pt.build();x.build();y.build();
}

int colour(int ar, int ac, int br, int bc) {
    swap(ac,br);

    if(ar==ac){
        return br-bc+1-pt.get(ar,ac,br,bc);
    }
    if(br==bc){
        return ar-ac+1-pt.get(ar,ac,br,bc);
    }
//    if(!pt.get(ar,ac,br,bc))
    int e=x.get(ar+1,ac,br,bc)+y.get(ar,ac,br+1,bc);
    int v=pt.get(ar,ac,br,bc);
    if(!v){
        return 1;
    }

    /// edges between от рамки
    e+=pt.get(ar,ar,br,bc)+pt.get(ac,ac,br,bc)+(bc-br+2)*2+(ar-ac+2)*2+4;
    e+=pt.get(ar,ac,br,br)+pt.get(ar,ac,bc,bc);

    ///
    v+=2*(bc-br+2)+(ar-ac+2)*2+4;

    int f=e-v+3-((pt.get(ar,ar,br,bc)>0 || pt.get(ac,ac,br,bc)>0) || (pt.get(ar,ac,br,br)>0 || pt.get(ar,ac,bc,bc)>0));
    f-=kv.get(ar+1,ac,br+1,bc);
    /// delete квадраты с рамкой
    f-=x.get(ar+1,ac,br,br);
    f-=x.get(ar+1,ac,bc,bc);

    f-=y.get(ar,ar,br+1,bc);
    f-=y.get(ac,ac,br+1,bc);

    f-=pt.get(ar,ar,bc,bc);
    f-=pt.get(ac,ac,bc,bc);
    f-=pt.get(ar,ar,br,br);
    f-=pt.get(ac,ac,br,br);

    --f;

//    cout<<"HERE "<<e<<' '<<v<<' '<<f<<endl;
    return f;
}
/*
4 4 6 1
2 2
NWWSSE
2 2 3 4
*/

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