Submission #130133

#	Time	Username	Problem	Language	Result	Execution time	Memory
130133		EntityIT	영역 (JOI16_ho_t4)	C++14	100 / 100	173 ms	12244 KiB

2016_ho_t4

#include<bits/stdc++.h>

using namespace std;

using ll = long long;
const ll infll = (ll)1e18 + 123;
int n, K, dx[] = { -1, 0, 1, 0 }, dy[] = { 0, 1, 0, -1 }, dir[200], a, b;
ll ans;
vector< array<ll, 4> > vecAns;
string s;

struct Type {
    ll r_x, r_y, q_f, q_l;
    Type (ll _r_x = 0, ll _r_y = 0, ll _q_f = 0, ll _q_l = 0) : r_x(_r_x), r_y(_r_y), q_f(_q_f), q_l(_q_l) {}
    bool operator< (const Type &_) const { return array<ll, 4>{ r_x, r_y, q_f, q_l } < array<ll, 4>{ _.r_x, _.r_y, _.q_f, _.q_l }; }
    bool operator> (const Type &_) const { return _ < *this; }
    bool operator== (const Type &_) const { return !(*this < _ || _ < *this); }
};
vector<Type> type;

void get (ll r_x, ll r_y, int _1, int _2) {
    int tmp = 0;
    if (r_x == a) {
        tmp = 1;
        r_x -= a;
        r_y -= b;
    }
    int pos = (int)(lower_bound(type.begin(), type.end(), Type(r_x, r_y, -infll, -infll) ) - type.begin() );
    for (; pos < (int)type.size() && array<ll, 2>{ r_x, r_y } == array<ll, 2>{ type[pos].r_x, type[pos].r_y }; ++pos) {
        vecAns.push_back(array<ll, 4>{ type[pos].q_f - tmp, _1, _2, 1 } );
        vecAns.push_back(array<ll, 4>{ type[pos].q_l + 1 - tmp, _1, _2, -1 } );
    }
}

void specCase () {
    set< array<ll, 2> > set_;
    for (int x = 0, y = 0, i = -1; i < n; ++i) {
        if (i >= 0) x += dx[ dir[ s[i] - 'A' ] ], y += dy[ dir[ s[i] - 'A' ] ];
        set_.insert(array<ll, 2>{ x, y } );
    }
    for (auto _ : set_) {
        ans += (set_.find(array<ll, 2>{ _[0] + 1, _[1] + 1 } ) != set_.end() &&
                set_.find(array<ll, 2>{ _[0], _[1] + 1 } ) != set_.end() &&
                set_.find(array<ll, 2>{ _[0] + 1, _[1] } ) != set_.end() );
    }
    cout << ans;
}

int32_t main () {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> K >> s;
    dir['E' - 'A'] = 2;
    dir['N' - 'A'] = 1;
    dir['W' - 'A'] = 0;
    dir['S' - 'A'] = 3;

    for (int i = 0; i < n; ++i) a += dx[ dir[ s[i] - 'A' ] ], b += dy[ dir[ s[i] - 'A' ] ];

    if (a < 0) {
        a = -a;
        for (int i = 0; i < n; ++i) {
            if (s[i] == 'E') s[i] = 'W';
            else if (s[i] == 'W') s[i] = 'E';
        }
    }

    if (b < 0) {
        b = -b;
        for (int i = 0; i < n; ++i) {
            if (s[i] == 'N') s[i] = 'S';
            else if (s[i] == 'S') s[i] = 'N';
        }
    }

    if (!a && !b) {
        specCase();
        return 0;
    }

    if (!a) {
        swap(a, b);
        for (int i = 0; i < n; ++i) {
            if (s[i] == 'E') s[i] = 'N';
            else if (s[i] == 'N') s[i] = 'E';
            else if (s[i] == 'W') s[i] = 'S';
            else if (s[i] == 'S') s[i] = 'W';
        }
    }

    for (int x = 0, y = 0, i = -1; i < n; ++i) {
        if (i >= 0) x += dx[ dir[ s[i] - 'A' ] ], y += dy[ dir[ s[i] - 'A' ] ];

        ll r_x, r_y, q_f, q_l;
        r_x = x % a;
        if (r_x < 0) r_x += a;
        q_f = (-r_x + x) / a;
        r_y = -(int)q_f * b + y;
        q_l = q_f + K - 1;

        type.push_back(Type(r_x, r_y, q_f, q_l) );
    }
    sort(type.begin(), type.end() ); type.erase(unique(type.begin(), type.end() ), type.end() );

    for (int i = 0; i < (int)type.size(); ++i) {
        vecAns.clear();
        get(type[i].r_x, type[i].r_y, 0, 0);
        get(type[i].r_x, type[i].r_y + 1, 0, 1);
        get(type[i].r_x + 1, type[i].r_y, 1, 0);
        get(type[i].r_x + 1, type[i].r_y + 1, 1, 1);

        int cnt[2][2], Cnt = 0; memset(cnt, 0, sizeof cnt);
        sort(vecAns.begin(), vecAns.end() );

        ll lst = -infll;
        for (auto _ : vecAns) {
            if (!cnt[ _[1] ][ _[2] ] && _[3] == 1) {
                if (Cnt == 3) lst = _[0];
                ++Cnt;
            }
            if (cnt[ _[1] ][ _[2] ] == 1 && _[3] == -1) {
                if (Cnt == 4) ans += _[0] - lst;
                --Cnt;
            }
            cnt[ _[1] ][ _[2] ] += (int)_[3];
        }
        for (int j = i + 1; j <= (int)type.size(); ++j) {
            if (j == (int)type.size() ) {
                i = j - 1;
                break ;
            }
            if (array<ll, 2>{ type[i].r_x, type[i].r_y } != array<ll, 2>{ type[j].r_x, type[j].r_y } ) {
                i = j - 1;
                break ;
            }
        }
    }

    cout << ans << '\n';

    return 0;
}

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