Submission #1163084

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163084		mispertion	영역 (JOI16_ho_t4)	C++20	0 / 100	2 ms	320 KiB

2016_ho_t4

#include <bits/stdc++.h>

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll = long long;
#define int ll
using ld = long double;
using pii = pair<int, int>;

#define S second
#define F first
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#define mispertion ios_base::sync_with_stdio(0),cin.tie(0)
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()

const ld PI = 3.1415926535;
const ld eps = 1e-9;
const int N = 3e5 + 2;
const int M = 1e4 + 13;
int mod =998244353;
const int infi = 1e9;
const ll infl = 1e16;
const int P = 3;

inline int mult(int a, int b) {
    return a * 1LL * b % mod; }

inline int sum(int a, int b) {
    if(a + b >= mod)
        return a + b - mod;
    if(a + b < 0)
        return a + b + mod;
    return a + b;
}

ll binpow(ll a, ll n, int mod) {
    if (n == 0) return 1;
    if (n % 2 == 1) {
        return binpow(a, n - 1, mod) * a % (mod);
    } else {
        ll b = binpow(a, n / 2, mod);
        return b * b % (mod);
    }
}

int n, k;
map<char, int> di, dj;
map<pair<int, pii>, vector<int>> sps;
vector<pii> pot = {{0, 0}, {0, -1}, {-1, -1}, {-1, 0}};
int dx = 0, dy = 0;
set<pii> al;

int get(int x, int y){
    int lo = 0, hi = 1e9+1;
    auto it = sps.find({x * dy - y * dx, {(x % (max(1LL, dx)) + (max(1LL, dx))) % (max(1LL, dx)), (y % (max(1LL, dy)) + (max(1LL, dy))) % (max(1LL, dy))}});
    if(it == sps.end()){
        return 1e9+1;
    }
    // for(auto e : it->S){
        // cout << e << ' ';
    // }
    // cout << '\n';
    auto r = lower_bound(all(it->S), x + y);
    while(lo + 1 < hi){
        int m = (lo + hi) / 2;
        auto l = lower_bound(all(it->S), x - m * dx + y - m * dy);
        if(r - l > 0){
            hi = m;
        }else{
            lo = m;
        }
    }
}

inline void solve() {
    cin >> n >> k;
    string s;
    cin >> s;
    di['W'] = 0;
    di['E'] = 0;
    di['E'] = 1;
    di['W'] = -1;
    dj['N'] = 1;
    dj['S'] = -1;
    dj['E'] = 0;
    dj['W'] = 0;
    for(auto c : s){
        dx += di[c];
        dy += dj[c];
    }
    if(dx == 0 && dy == 0){
        set<pii> st;
        int i = 0, j = 0;
        int pr = 0;
        for(int _ = 1; _ <= 1; _++){
            st.insert({i, j});
            for(auto c : s){
                i += di[c];
                j += dj[c];
                st.insert({i, j});
            }
            int ans = 0;
            for(auto e : st){
                if(st.find({e.F, e.S + 1}) != st.end() &&
                st.find({e.F + 1, e.S}) != st.end() && 
                st.find({e.F + 1, e.S + 1}) != st.end())
                    ans++;
            }
            pr = ans;
        }
        cout << pr << '\n';
        return;
    }
    if(dx < 0){
        for(auto &c : s){
            if(c == 'W'){
                c = 'E';
            }else if(c == 'E'){
                c = 'W';
            }
        }
    }
    if(dy < 0){
        for(auto &c : s){
            if(c == 'N')
                c = 'S';
            else if(c == 'S')
                c = 'N';
        }
    }
    dx = 0, dy = 0;
    al.insert({0, 0});
    for(auto c : s){
        dx += di[c];
        dy += dj[c];
        al.insert({dx, dy});
        pot.push_back({dx, dy});
        pot.push_back({dx - 1, dy});
        pot.push_back({dx, dy - 1});
        pot.push_back({dx - 1, dy - 1});
    }
    sort(all(pot));
    pot.resize(unique(all(pot)) - pot.begin());
    sps[{0LL, {0LL, 0LL}}].push_back(0);
    int x = 0, y = 0;
    for(auto c : s){
        x += di[c];
        y += dj[c];
        sps[{x * dy - y * dx, {(x % (max(1LL, dx)) + (max(1LL, dx))) % (max(1LL, dx)), (y % (max(1LL, dy)) + (max(1LL, dy))) % (max(1LL, dy))}}].push_back(x + y);
    }

    for(auto e : sps){
        sort(all(sps[e.F]));
    }
    int ans = 0;
    // cout << dx << ' ' << dy << '\n';
    for(auto e : pot){
        int x = e.F, y = e.S;
        int r = -1, l = 0;
        // cout << x << ' ' << y << '\n';
        if(al.find({x, y}) != al.end()){
            r = max(r, get(x, y));
        }else{
            l = max(l, get(x, y));
        }
        if(al.find({x + 1, y}) != al.end()){
            r = max(r, get(x + 1, y));
        }else{
            l = max(l, get(x + 1, y));
        }
        if(al.find({x, y + 1}) != al.end()){
            r = max(r, get(x, y + 1));
        }else{
            l = max(l, get(x, y + 1));
        }
        if(al.find({x + 1, y + 1}) != al.end()){
            r = max(r, get(x + 1, y + 1));
        }else{
            l = max(l, get(x + 1, y + 1));
        }
        // cout << l << ' ' << r << '\n';
        r = min(r, k);
        if(l < r)
            ans += r - l;
    }
    // cout << '\n';
    // cout << get(1, 1) << ' ';
    cout << ans << '\n';
}

signed main() {
    mispertion;
    int t = 1;
    //cin >> t;
    for(int i = 1; i <= t; i ++){
        solve();
    }
    return 0;
}

Compilation message (stderr)

2016_ho_t4.cpp: In function 'll get(ll, ll)':
2016_ho_t4.cpp:77:1: warning: control reaches end of non-void function [-Wreturn-type]
   77 | }
      | ^

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