結果

問題 No.1405 ジグザグロボット
ユーザー Enucai
提出日時 2025-03-27 00:03:03
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 17 ms / 3,153 ms
コード長 6,400 bytes
コンパイル時間 3,179 ms
コンパイル使用メモリ 218,840 KB
実行使用メモリ 39,956 KB
最終ジャッジ日時 2025-03-27 00:03:13
合計ジャッジ時間 8,701 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
using ll = long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;

template<class T> void chkmn(T &x, T y) { if (y < x) x = y; }
template<class T> void chkmx(T &x, T y) { if (y > x) x = y; }

using namespace std;

const int maxn = 300010;

struct segtree {
  int t[maxn << 2], lz[maxn << 2];

  #define mid ((l + r) >> 1)

  void build(int c, int l, int r) {
    lz[c] = 0;
    if (l == r) return t[c] = 0, void();
    build(c << 1, l, mid), build(c << 1 | 1, mid + 1, r);
    t[c] = min(t[c << 1], t[c << 1 | 1]);
  }

  void down(int c) {
    if (!lz[c]) return;
    t[c << 1] += lz[c], lz[c << 1] += lz[c];
    t[c << 1 | 1] += lz[c], lz[c << 1 | 1] += lz[c];
    lz[c] = 0;
  }

  void upd(int c, int l, int r, int x, int y, int v) {
    if (l == x && r == y) return t[c] += v, lz[c] += v, void();
    down(c);
    if (y <= mid) upd(c << 1, l, mid, x, y, v);
    else if (x > mid) upd(c << 1 | 1, mid + 1, r, x, y, v);
    else upd(c << 1, l, mid, x, mid, v), upd(c << 1 | 1, mid + 1, r, mid + 1, y, v);
    t[c] = min(t[c << 1], t[c << 1 | 1]);
  }

  int find(int c, int l, int r) {
    if (t[c]) return -1;
    if (l == r) return l;
    int res = find(c << 1, l, mid);
    if (res != -1) return res;
    return find(c << 1 | 1, mid + 1, r);
  }

  #undef mid
} seg;

int n, X, Y, tot, pos[maxn], L[maxn], R[maxn], from[maxn], vis[maxn], delta[maxn], gx[maxn];
pll t[maxn << 2];
ll lz[maxn << 2], f[maxn], g[maxn];
string str, s[maxn];
vector<pii> ans, vec[maxn];

#define mid ((l + r) >> 1)

void build(int c, int l, int r) {
  lz[c] = 0;
  if (l == r) return t[c] = pll(-1e18, l - 1), void();
  build(c << 1, l, mid), build(c << 1 | 1, mid + 1, r);
  t[c] = max(t[c << 1], t[c << 1 | 1]);
}

void down(int c) {
  if (!lz[c]) return;
  t[c << 1].fi += lz[c], lz[c << 1] += lz[c];
  t[c << 1 | 1].fi += lz[c], lz[c << 1 | 1] += lz[c];
  lz[c] = 0;
}

void cg(int c, int l, int r, int x, ll v) {
  if (l == r) return t[c] = pll(v, l - 1), void();
  down(c);
  if (x <= mid) cg(c << 1, l, mid, x, v);
  else cg(c << 1 | 1, mid + 1, r, x, v);
  t[c] = max(t[c << 1], t[c << 1 | 1]);
}

void upd(int c, int l, int r, int x, int y, ll v) {
  if (l == x && r == y) return t[c].fi += v, lz[c] += v, void();
  down(c);
  if (y <= mid) upd(c << 1, l, mid, x, y, v);
  else if (x > mid) upd(c << 1 | 1, mid + 1, r, x, y, v);
  else upd(c << 1, l, mid, x, mid, v), upd(c << 1 | 1, mid + 1, r, mid + 1, y, v);
  t[c] = max(t[c << 1], t[c << 1 | 1]);
}

pll qry(int c, int l, int r, int x, int y) {
  if (l == x && r == y) return t[c];
  down(c);
  if (y <= mid) return qry(c << 1, l, mid, x, y);
  else if (x > mid) return qry(c << 1 | 1, mid + 1, r, x, y);
  else return max(qry(c << 1, l, mid, x, mid), qry(c << 1 | 1, mid + 1, r, mid + 1, y));
}

#undef mid

pll calc(ll mid) {
  build(1, 1, tot), f[0] = g[0] = 0;
  rep (i, 1, tot) {
    cg(1, 1, tot, i, f[i - 1]);
    for (auto s : vec[i]) upd(1, 1, tot, 1, s.fi, s.se);
    auto s = qry(1, 1, tot, 1, i);
    from[i] = s.se, f[i] = s.fi - mid, g[i] = g[s.se] + 1;
  }
  return pll(f[tot], g[tot]);
}

int main() {
  cin.tie(nullptr) -> ios::sync_with_stdio(false);
  cin >> n >> X >> Y >> str, tot = 1;
  for (char c : str) {
    if (c == 'S') tot++;
    else s[tot] += c;
  }
  if (tot <= Y) return cout << "-1\n", 0;
  seg.build(1, 1, tot);
  rep (i, 1, tot) {
    for (char c : s[i]) {
      if (c == 'L') {
        int lim = seg.find(1, 1, tot);
        if (lim == -1) lim = i + 1;
        if (lim > 1) {
          vec[i].emplace_back(lim - 1, -1);
          seg.upd(1, 1, tot, 1, lim - 1, -1);
        }
      } else {
        vec[i].emplace_back(i, 1);
        seg.upd(1, 1, tot, 1, i, 1);
      }
    }
  }
  int l = 0, r = n, slope = 0;
  while (l <= r) {
    int mid = (l + r) >> 1;
    auto res = calc(mid);
    if (res.se >= Y + 1) slope = mid, l = mid + 1;
    else r = mid - 1;;
  }
  auto xres = calc(slope), yres = calc(slope + 1);
  ll DP;
  if (xres.se == Y + 1) {
    DP = xres.fi + 1ll * slope * xres.se;
  } else {
    ll xl = xres.se, yl = xres.fi + 1ll * slope * xres.se;
    ll xr = yres.se, yr = yres.fi + 1ll * (slope + 1) * yres.se;
    DP = yl + (yr - yl) * (Y + 1 - xl) / (xr - xl);
  }
  if (DP < X) return cout << "-1\n", 0;
  vector<int> dpos, cpos;
  int cur = tot;
  while (cur) cur = from[cur], dpos.emplace_back(cur + 1);
  for (int x : dpos) vis[x] = 1;
  calc(slope);
  cur = tot;
  while (cur) cur = from[cur], cpos.emplace_back(cur + 1);
  for (int x : cpos) if (!vis[x] && SZ(dpos) < Y + 1) dpos.emplace_back(x);
  sort(ALL(dpos));
  rep (i, 0, Y) pos[i] = dpos[i];
  pos[Y + 1] = tot + 1, cur = 0;
  rep (i, 0, Y) {
    int mn = cur, mx = cur, pre = cur;
    rep (j, pos[i], pos[i + 1] - 1) {
      for (char c : s[j]) {
        if (c == 'L') cur--;
        else cur++;
        chkmx(cur, pre), chkmn(mn, cur), chkmx(mx, cur);
      }
    }
    L[i] = mn, R[i] = mx;
  }
  int rest = DP - X;
  per (i, Y, 0) if (rest) {
    int cur = L[i];
    rep (j, pos[i], pos[i + 1] - 1) {
      for (char c : s[j]) {
        if (c == 'L') cur--;
        else cur++;
        chkmx(cur, L[i]), chkmn(cur, R[i]);
      }
    }
    int l = 1, r = R[i] - L[i], res = 0;
    while (l <= r) {
      int mid = (l + r) >> 1, tmp = L[i];
      rep (j, pos[i], pos[i + 1] - 1) {
        for (char c : s[j]) {
          if (c == 'L') tmp--;
          else tmp++;
          chkmx(tmp, L[i]), chkmn(tmp, R[i] - mid);
        }
      }
      if (cur - tmp <= rest) res = mid, l = mid + 1;
      else r = mid - 1;
    }
    R[i] -= res;
    int tmp = L[i];
    rep (j, pos[i], pos[i + 1] - 1) {
      for (char c : s[j]) {
        if (c == 'L') tmp--;
        else tmp++;
        chkmx(tmp, L[i]), chkmn(tmp, R[i]);
      }
    }
    gx[i] = cur - tmp, rest -= cur - tmp;
  }
  int psum = 0;
  rep (i, 0, Y) L[i] -= psum, R[i] -= psum, psum += gx[i];
  rep (i, 0, Y) {
    ans.emplace_back(L[i] - 1, i), ans.emplace_back(R[i] + 1, i);
    rep (j, L[i], R[i]) if (i == Y || j < L[i + 1] || j > R[i + 1]) ans.emplace_back(j, i + 1);
  }
  sort(ALL(ans)), ans.erase(unique(ALL(ans)), ans.end());
  cout << SZ(ans) << '\n';
  for (auto s : ans) cout << s.fi << ' ' << s.se << '\n';
}
0