oj.uz

Submission #51834

# Submission time Handle Problem Language Result Execution time Memory
51834 2018-06-21T13:15:56 Z Diuven None (JOI16_ho_t4) C++11
0 / 100
 4 ms 568 KB 
#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)]);
        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, pii> T;
map<pii, bool> occ;

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

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);
    }
    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];
            if(!occ[pii(u,v)]) l=1, r=0;
            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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 3 ms 392 KB Output is correct
4 Correct 3 ms 568 KB Output is correct
5 Correct 4 ms 568 KB Output is correct
6 Correct 2 ms 568 KB Output is correct
7 Correct 3 ms 568 KB Output is correct
8 Incorrect 3 ms 568 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 3 ms 392 KB Output is correct
4 Correct 3 ms 568 KB Output is correct
5 Correct 4 ms 568 KB Output is correct
6 Correct 2 ms 568 KB Output is correct
7 Correct 3 ms 568 KB Output is correct
8 Incorrect 3 ms 568 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 3 ms 392 KB Output is correct
4 Correct 3 ms 568 KB Output is correct
5 Correct 4 ms 568 KB Output is correct
6 Correct 2 ms 568 KB Output is correct
7 Correct 3 ms 568 KB Output is correct
8 Incorrect 3 ms 568 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 3 ms 392 KB Output is correct
4 Correct 3 ms 568 KB Output is correct
5 Correct 4 ms 568 KB Output is correct
6 Correct 2 ms 568 KB Output is correct
7 Correct 3 ms 568 KB Output is correct
8 Incorrect 3 ms 568 KB Output isn't correct
9 Halted 0 ms 0 KB -