Submission #1216862


Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define all(v) begin(v), end(v)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reps(i, s, n) for(int i = (int)(s); i < (int)(n); i++)

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

using pint = pair<int, int>;
using tint = tuple<int, int, int>;
using vint = vector<int>;

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

struct SegT {
  vector<int> data;
  int sz;
  SegT(){}
  void init(int n) {
    sz = 1; while(sz < n) sz<<=1;
    data.resize(2*sz+1, inf);
  }
  void update(int k, int x) {
    k += sz-1;
    data[k] = x;
    while(k > 0) {
      k = (k-1) / 2;
      data[k] = min(data[2*k+1], data[2*k+2]);
    }
  }
  int query(int a, int b, int k, int l, int r) {
    if(r <= a || b <= l) return inf;
    if(a <= l && r <= b) return data[k];
    int vl = query(a, b, 2*k+1, l, (l+r)/2);
    int vr = query(a, b, 2*k+2, (l+r)/2, r);
    return min(vl, vr);
  }
  int query(int a, int b) {
    return query(a, b, 0, 0, sz);
  }
};

int N, Q;
string S;
SegT sgO, sgC;
vint os, cs, hs;

int binsearch(int l, int r, int tar) {
  int lb = l, ub = r;
  while(lb + 1 < ub) {
    int mb = (lb + ub) / 2;
    if(hs[mb] >= tar) ub = mb;
    else lb = mb;
  }
  return (ub == N ? -1 : ub);
}

bool check(int l, int r) {
  int len = r - l;
  if(len%2 == 1) return false; // 奇数長区間は無理
  len /= 2;

  int onum = os[r-1] - os[l-1]; // 区間上の確定(の数
  int cnum = cs[r-1] - cs[l-1]; // 区間上の確定)の数
  if(len < onum || len < cnum) return false; // ()の数をlenと同じにしたい
  // 列の半分が(/)なら区間上の?は全部)/(にして途中で-1以下になってなければ良い
  if(len == onum) return sgC.query(l-1, r) >= sgC.query(r-1, r);
  if(len == cnum) return sgO.query(l-1, r) >= sgO.query(l-1, l);

  int h2o = len - onum;
  int idx = binsearch(l-1, r, h2o + hs[l-1]); // 左からh2oだけ?->(時の最後の位置
  if(~idx) return sgO.query(l-1, r) >= sgO.query(l-1, l);
  return (sgO.query(l-1, idx+1) >= sgO.query(l-1, l) &&
	  sgC.query(idx+1, r) >= sgC.query(r-1, r));
}

signed main()
{
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  cin >> N >> S;

  os.resize(N+1); // (の累積和
  cs.resize(N+1); // )の累積和
  hs.resize(N+1); // ?の累積和
  rep(i, N) {
    os[i+1] = os[i] + (S[i] == '(');
    cs[i+1] = cs[i] + (S[i] == ')');
    hs[i+1] = hs[i] + (S[i] == '?');
  }

  sgO.init(N+1); // ?->(にした時の括弧値のRMQ
  sgC.init(N+1); // ?->)にした時の括弧値のRMQ
  sgO.update(0, 0);
  sgC.update(0, 0);
  int h2o = 0, h2c = 0;
  rep(i, N) {
    if(S[i] == '(') h2o++, h2c++; // (->+1
    else if(S[i] == ')') h2o--, h2c--; // )->-1
    else h2o++, h2c--; // ?->+1/-1
    sgO.update(i+1, h2o);
    sgC.update(i+1, h2c);
  }

  cin >> Q;
  rep(i, Q) {
    int l, r;
    cin >> l >> r; r++;
    cout << (check(l, r) ? "Yes" : "No") << endl;
  }

  return 0;
}

Submission Info

Submission Time
Task D - Parenthesis Sequence
User ukuku09
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3187 Byte
Status WA
Exec Time 299 ms
Memory 7248 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 100
Status
AC × 2
AC × 9
WA × 20
Set Name Test Cases
Sample sample_01.txt, sample_02.txt
All sample_01.txt, sample_02.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
test_01.txt AC 164 ms 512 KB
test_02.txt AC 158 ms 512 KB
test_03.txt AC 165 ms 512 KB
test_04.txt AC 179 ms 7248 KB
test_05.txt AC 184 ms 7248 KB
test_06.txt AC 214 ms 7248 KB
test_07.txt AC 260 ms 7248 KB
test_08.txt WA 262 ms 7248 KB
test_09.txt WA 258 ms 7248 KB
test_10.txt WA 258 ms 7248 KB
test_11.txt WA 264 ms 7248 KB
test_12.txt WA 256 ms 7248 KB
test_13.txt WA 261 ms 7248 KB
test_14.txt WA 256 ms 7248 KB
test_15.txt WA 266 ms 7248 KB
test_16.txt WA 260 ms 7248 KB
test_17.txt WA 299 ms 7248 KB
test_18.txt WA 260 ms 7248 KB
test_19.txt WA 259 ms 7248 KB
test_20.txt WA 258 ms 7248 KB
test_21.txt WA 263 ms 7248 KB
test_22.txt WA 254 ms 7248 KB
test_23.txt WA 211 ms 7168 KB
test_24.txt WA 196 ms 7040 KB
test_25.txt WA 215 ms 7040 KB
test_26.txt WA 207 ms 7040 KB
test_27.txt WA 205 ms 7168 KB