Submission #51832

#	Time	Username	Problem	Language	Result	Execution time	Memory
51832		Diuven	영역 (JOI16_ho_t4)	C++11	0 / 100	2 ms	488 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+1,y)] && B[pii(x+1,y)]);
        C[pii(x,y)]=true;
    }
    cout<<ans;
    exit(0);
}

void flip_h(){
    for(int i=1; i<=n; i++)
        X[i]=-X[i];
}
void flip_v(){
    for(int i=1; i<=n; i++)
        Y[i]=-Y[i];
}
void flip_x(){
    for(int i=1; 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, pii> T;

void put(int x, int y, int l, int r){
    pii &p=T[pii(x,y)];
    p.first=min(p.first, l);
    p.second=max(p.second, r);
}

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;
        T[pii(x,y)]=pii(inf, -inf);
        if(x==0) T[pii(x+a,y+b)]=pii(inf,-inf);
    }
    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);
    }
    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;
        int l=-inf, r=inf;
        for(int k=0; k<4; k++){
            int u=x+dx[k], v=y+dy[k];
            l=max(l, T[pii(u,v)].first);
            r=min(r, T[pii(u,v)].second);
        }
        ans+=max(r-l+1, 0);
    }
    return ans;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    init();
    cout<<solve();
    return 0;
}

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