Submission #51998

#	Time	Username	Problem	Language	Result	Execution time	Memory
51998		Diuven	영역 (JOI16_ho_t4)	C++11	100 / 100	237 ms	31108 KiB

2016_ho_t4

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=100010, inf=2e9;

const int dx[4]={0,1,1,0};
const int dy[4]={0,0,1,1};
int n, k;
int X[MX], Y[MX];
pii disp;

void solve0(){
    int ans=0;
    map<pii, bool> B, C;
    for(int i=0; i<=n; i++){
        B[pii(X[i], Y[i])]=true;
    }
    for(int i=0; i<=n; i++){
        int x=X[i], y=Y[i];
        ans+=(!C[pii(x,y)] && B[pii(x+1,y)] && B[pii(x,y+1)] && B[pii(x+1,y+1)]);
        // if(!C[pii(x,y)] && B[pii(x+1,y)] && B[pii(x,y+1)] && B[pii(x+1,y+1)])
        //     cout<<x<<' '<<y<<'\n';
        C[pii(x,y)]=true;
    }
    cout<<ans;
    exit(0);
}

void flip_h(){
    for(int i=0; i<=n; i++)
        X[i]=-X[i];
}
void flip_v(){
    for(int i=0; i<=n; i++)
        Y[i]=-Y[i];
}
void flip_x(){
    for(int i=0; i<=n; i++)
        swap(X[i], Y[i]);
}
void trans(){
    int xmn=inf, ymn=inf;
    for(int i=0; i<=n; i++)
        xmn=min(xmn, X[i]), ymn=min(ymn, Y[i]);
    for(int i=0; i<=n; i++)
        X[i]-=xmn, Y[i]-=ymn;
}

void norm(int a, int b){
    if(a==0 && b==0) solve0();
    if(a<0) flip_h(), a=abs(a);
    if(b<0) flip_v(), b=abs(b);
    if(a==0) flip_x(), swap(a,b);
    trans();
    disp=pii(a, b);
    for(int i=0; i<=n; i++)
        X[i]+=a, Y[i]+=b;
}

void init(){
    cin>>n>>k;
    int x=0, y=0;
    for(int i=1; i<=n; i++){
        char c; cin>>c;
        if(c=='S') y--;
        if(c=='N') y++;
        if(c=='W') x--;
        if(c=='E') x++;
        X[i]=x, Y[i]=y;
    }
    norm(x,y);
}

map<pii, vector<pii> > T;

void put(int x, int y, int l, int r){
    auto &V=T[pii(x,y)];
    V.push_back(pii(l,r));
}

void intst(map<int, int> &A, const vector<pii> &B){
    for(const pii &p:B){
        int l,r; tie(l,r)=p;
        A[l]++, A[r+1]--;
    }
}

void unite(vector<pii> &V){
    sort(V.begin(), V.end());
    vector<pii> W;
    for(pii &p:V){
        if(W.empty()) W.push_back(p);
        else{
            int l,r; tie(l,r)=p;
            pii &q=W[W.size()-1U];
            if(q.second<l-1) W.push_back(p);
            else q=pii(q.first, max(q.second, r));
        }
    }
    V=W;
}

void show(vector<pii> &V){
    for(pii &p:V)
        cout<<p.first<<" ~ "<<p.second<<", ";
    cout<<'\n';
}

ll solve(){
    ll ans=0;
    int a, b; tie(a,b)=disp; // != 0

    for(int i=0; i<=n; i++){
        int q=X[i]/a, x=X[i]-q*a, y=Y[i]-q*b;
        put(x, y, q, q+k-1);
        if(x==0) put(x+a, y+b, q-1, q+k-2);
    }
    for(int i=0; i<=n; i++){
        int q=X[i]/a, x=X[i]-q*a, y=Y[i]-q*b;
        unite(T[pii(x,y)]);
        // cout<<x<<' '<<y<<": ";
        // show(T[pii(x,y)]);
        if(x==0) unite(T[pii(x+a,y+b)]);
    }
    map<pii, bool> done;

    for(int i=0; i<=n; i++){
        int q=X[i]/a, x=X[i]-q*a, y=Y[i]-q*b;
        if(done[pii(x,y)]) continue;
        done[pii(x,y)]=true;

        map<int, int> B;

        for(int k=0; k<4; k++){
            int u=x+dx[k], v=y+dy[k];
            intst(B, T[pii(u,v)]);
        }
        int now=0, prv=-inf, cnt=0;
        for(pii p:B){
            int x, diff; tie(x,diff)=p;
            if(cnt==4) now+=x-prv;
            cnt+=diff;
            prv=x;
        }
        // if(now!=0)
        //     cout<<X[i]<<' '<<Y[i]<<": "<<now<<'\n';
        ans+=now;
    }
    return ans;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    init();
    // cout<<"\nDISP: "<<disp.first<<' '<<disp.second<<'\n';
    cout<<solve()<<'\n';
    // solve0();
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 62 / 62