oj.uz

Submission #51997

# Submission time Handle Problem Language Result Execution time Memory
51997 2018-06-23T04:51:42 Z Diuven None (JOI16_ho_t4) C++11
0 / 100
 3 ms 644 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)]);
        // 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(vector<pii> &A, const vector<pii> &B){
    vector<pii> C;
    int pos=0, sz=A.size();
    for(const pii &p:B){
        int l,r; tie(l,r)=p;
        while(pos<sz && A[pos].second<l) pos++;
        while(pos<sz && A[pos].first<=r){
            int s,e; tie(s,e)=A[pos];
            C.push_back(pii(max(s,l), min(e,r)));
            pos++;
        }
    }
    A=C;
}

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;
}

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)]);
        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;

        vector<pii> L;
        L.push_back(pii(-inf, inf));
        for(int k=0; k<4; k++){
            int u=x+dx[k], v=y+dy[k];
            intst(L, T[pii(u,v)]);
        }
        int now=0;
        for(pii &p:L)
            now+=p.second-p.first+1;
        ans+=now;
    }
    return ans;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    init();
    cout<<solve()<<'\n';
    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 408 KB Output is correct
4 Correct 3 ms 456 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 2 ms 568 KB Output is correct
7 Correct 2 ms 644 KB Output is correct
8 Incorrect 2 ms 644 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 408 KB Output is correct
4 Correct 3 ms 456 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 2 ms 568 KB Output is correct
7 Correct 2 ms 644 KB Output is correct
8 Incorrect 2 ms 644 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 408 KB Output is correct
4 Correct 3 ms 456 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 2 ms 568 KB Output is correct
7 Correct 2 ms 644 KB Output is correct
8 Incorrect 2 ms 644 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 408 KB Output is correct
4 Correct 3 ms 456 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 2 ms 568 KB Output is correct
7 Correct 2 ms 644 KB Output is correct
8 Incorrect 2 ms 644 KB Output isn't correct
9 Halted 0 ms 0 KB -