Submission #202379

#	Time	Username	Problem	Language	Result	Execution time	Memory
202379		fedoseevtimofey	영역 (JOI16_ho_t4)	C++14	100 / 100	342 ms	34424 KiB

2016_ho_t4

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <cassert>
#include <complex>
#include <functional>
 
using namespace std;
 
typedef long long ll;

pair <int, int> get(char c) {
  if (c == 'N') return {-1, 0};
  else if (c == 'S') return {1, 0};
  else if (c == 'W') return {0, -1};
  else return {0, 1};
}

int cnt(string s) {
  set <pair <int, int>> vis;
  int x = 0, y = 0;
  vis.insert({x, y});
  for (char c : s) {
    x += get(c).first;
    y += get(c).second;
    vis.insert({x, y});
  }
  int cnt = 0;
  for (auto p : vis) {
    int x = p.first;
    int y = p.second;
    if (vis.count({x + 1, y}) && vis.count({x, y + 1}) && vis.count({x + 1, y + 1})) {
      ++cnt;
    }
  }
  return cnt;
}

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
  int n, k;
  cin >> n >> k;
  string s;
  cin >> s;
  vector <int> px(n + 1), py(n + 1);
  for (int i = 0; i < n; ++i) {
    px[i + 1] = px[i] + get(s[i]).first;
    py[i + 1] = py[i] + get(s[i]).second;
  }
  int cx = px.back();
  int cy = py.back();
  if (cx == 0 && cy == 0) {
    cout << cnt(s) << '\n';
    return 0;
  }
  if (cx == 0) {
    swap(cx, cy);
    for (int i = 0; i <= n; ++i) swap(px[i], py[i]);
  }
  if (cx < 0) {
    cx *= -1;
    for (int i = 0; i <= n; ++i) px[i] *= -1;
  }
  if (cy < 0) {
    cy *= -1;
    for (int i = 0; i <= n; ++i) py[i] *= -1;
  }
  map <pair <int, int>, vector <pair <int, int>>> mp;
  auto get = [&] (int x, int y) {
    int rem = (x % cx + cx) % cx;
    int cnt = (rem - x) / cx;
    y += cnt * cy;
    x = rem;
    return make_pair(x, y);
  };

  for (int i = 0; i <= n; ++i) {
    auto pr = get(px[i], py[i]);
    int x = pr.first, y = pr.second;
    int cnt = (px[i] - x) / cx;
    mp[{x, y}].push_back({cnt, cnt + k - 1});
    mp[{x + cx, y + cy}].push_back({cnt - 1, cnt + k - 2});
    mp[{x - cx, y - cy}].push_back({cnt + 1, cnt + k});
  }
  auto hv = [&] (int x, int y, int t) {
    if (!mp.count({x, y})) return false;
    for (auto p : mp[{x, y}]) {
      if (p.first <= t && t <= p.second) return true;
    }
    return false;
  };

  for (auto &pr : mp) {
    vector <pair <int, int>> ev;
    for (auto [l, r] : pr.second) {
      ev.emplace_back(l, -1);
      ev.emplace_back(r, 1);
    }
    sort(ev.begin(), ev.end());
    int bal = 0;
    pr.second.clear();
    int lst = 0;
    for (auto p : ev) {
      if (p.second == -1) {
        ++bal;
        if (bal == 1) lst = p.first;
      } else {
        --bal;
        if (bal == 0) pr.second.emplace_back(lst, p.first);
      }
    }
  }

  ll ans = 0;
  for (auto pr : mp) {
    int x = pr.first.first;
    int y = pr.first.second;
    if (make_pair(x, y) != get(x, y)) continue;
    if (!mp.count({x, y}) || !mp.count({x + 1, y}) || !mp.count({x, y + 1}) || !mp.count({x + 1, y + 1})) continue;
    vector <pair <int, int>> ev;
    for (auto pr : mp[{x, y}]) {
      ev.push_back({pr.first, -1});
      ev.push_back({pr.second, 1});
    }
    for (auto pr : mp[{x + 1, y}]) {
      ev.push_back({pr.first, -1});
      ev.push_back({pr.second, 1});
    }
    for (auto pr : mp[{x, y + 1}]) {
      ev.push_back({pr.first, -1});
      ev.push_back({pr.second, 1});
    }
    for (auto pr : mp[{x + 1, y + 1}]) {
      ev.push_back({pr.first, -1});
      ev.push_back({pr.second, 1});
    }
    sort(ev.begin(), ev.end());
    int lst = 0, bal = 0;
    for (auto p : ev) {
      if (p.second == -1) {
        ++bal;
        if (bal == 4) lst = p.first;
      } else {
        --bal;
        if (bal == 3) ans += p.first - lst + 1;
      }
    }
  }
  cout << ans << '\n';
}

Compilation message (stderr)

2016_ho_t4.cpp: In function 'int main()':
2016_ho_t4.cpp:111:15: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
     for (auto [l, r] : pr.second) {
               ^
2016_ho_t4.cpp:101:8: warning: variable 'hv' set but not used [-Wunused-but-set-variable]
   auto hv = [&] (int x, int y, int t) {
        ^~

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