Submission #130116

#	Time	Username	Problem	Language	Result	Execution time	Memory
130116		EntityIT	영역 (JOI16_ho_t4)	C++14	0 / 100	2 ms	376 KiB

2016_ho_t4

#include<bits/stdc++.h>

using namespace std;

#define int ll

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;
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 }; }
};
vector<Type> type, _type;

ll get_frst (ll r_x, ll r_y) {
    if (r_x == a) {
        r_x -= a;
        r_y -= b;
    }
    int pos = (int)(lower_bound(type.begin(), type.end(), Type(r_x, r_y, -infll, -infll) ) - type.begin() );
    if (pos == (int)type.size() || array<ll, 2>{ r_x, r_y } != array<ll, 2>{ type[pos].r_x, type[pos].r_y } ) return infll;
    else return type[pos].q_f;
}

ll get_lst (ll r_x, ll r_y) {
    if (r_x == a) {
        r_x -= a;
        r_y -= b;
    }
    int pos = (int)(lower_bound(type.begin(), type.end(), Type(r_x, r_y, -infll, -infll) ) - type.begin() );
    if (pos == (int)type.size() || array<ll, 2>{ r_x, r_y } != array<ll, 2>{ type[pos].r_x, type[pos].r_y } ) return -infll;
    else return type[pos].q_l;
}

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


//    freopen("test.INP", "r", stdin);
////    freopen("Seeht.OUT", "w", stdout);

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

//    cout << "a = " << a <<  "  b = " << b << '\n';

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

    for (int i = 0; i < (int)type.size(); ++i) {
        for (int _i = i + 1; _i <= (int)type.size(); ++_i) {
            if (_i == (int)type.size() || array<ll, 2>{ type[i].r_x, type[i].r_y } != array<ll, 2>{ type[_i].r_x, type[_i].r_y }) {
                _type.push_back(Type(type[i].r_x, type[i].r_y, type[i].q_f, type[_i - 1].q_l) );
                i = _i - 1;
                break ;
            }
        }
    }
    type = _type;

    for (int i = 0; i < (int)type.size(); ++i) {
        ll frst = type[i].q_f, lst = type[i].q_l;

        frst = max(frst, get_frst(type[i].r_x + 1, type[i].r_y + 1) - (type[i].r_x + 1 == a) );
        lst = min(lst, get_lst(type[i].r_x + 1, type[i].r_y + 1) - (type[i].r_x + 1 == a) );

        frst = max(frst, get_frst(type[i].r_x, type[i].r_y + 1) );
        lst = min(lst, get_lst(type[i].r_x, type[i].r_y + 1) );

        frst = max(frst, get_frst(type[i].r_x + 1, type[i].r_y) - (type[i].r_x + 1 == a) );
        lst = min(lst, get_lst(type[i].r_x + 1, type[i].r_y) - (type[i].r_x + 1 == a) );

        ans += max(0LL, lst - frst + 1);
    }

    cout << ans << '\n';

    return 0;
}

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