Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <stdio.h>
- #include <algorithm>
- #include <cmath>
- #include <set>
- #include <map>
- #include <bitset>
- #include <vector>
- #include <queue>
- #include <memory.h>
- #include <deque>
- #include <iomanip>
- #include <utility>
- #include <string>
- #include <ext/rope>
- #include <iterator>
- using namespace std;
- using namespace __gnu_cxx;
- #define pb push_back
- #define mp make_pair
- #define F first
- #define S second
- #define sz size
- #define scf scanf
- #define prf printf
- #define all(x) x.begin(), x.end()
- #define rall(x) x.rbegin(), x.rend()
- #define gcd(a,b) __gcd(a,b)
- #define print(x) prf("%d\n", x.sz()); for (int i = 0; i < x.sz(); i++) prf("%d ", x[i]);
- #define getBit(x,i) ((x&(1<<i))!=0 ? 1 : 0)
- #define For(i,n) for (int i = 0; i < n; ++i)
- #define FOR(i,begin,end,move) for (int i = begin; i != end; i += move)
- typedef long long ll;
- const ll base = 1000000007LL;
- const ll INF = 10000000000000LL;
- int q;
- int l, r;
- int cnt = 0;
- int curPos;
- string s;
- int typeOf[100500];
- bool used[100500] = {false};
- int next[100500] = {0};
- vector < pair < int, char > > st;
- vector < int > g[100500];
- bool canFind(int pos, int data)
- {
- int l = 0;
- int r = g[pos].sz() - 1;
- if (min(l, r) < 0)
- return false;
- while (l < r)
- {
- int mid = (l + r) >> 1;
- if (g[pos][mid] >= data)
- r = mid;
- else l = mid + 1;
- }
- return g[pos][l] == data;
- }
- int main()
- {
- ios_base::sync_with_stdio(false);
- getline(cin, s);
- For(i, s.sz())
- {
- if (st.sz() > 0)
- {
- if (st.back().S - 'A' == s[i] - 'a')
- {
- next[st.back().F] = i + 1;
- st.pop_back();
- continue;
- }
- }
- st.pb(mp(i + 1, s[i]));
- }
- int n = s.sz();
- For(i, n + 1)
- if (!used[i] && next[i] != 0)
- {
- cnt++;
- curPos = i;
- while (true)
- {
- if (next[curPos] == 0)
- break;
- used[curPos] = true;
- typeOf[curPos] = cnt;
- g[cnt].pb(next[curPos]);
- curPos = next[curPos] + 1;
- }
- }
- cin >> q;
- while (q--)
- {
- cin >> l >> r;
- if (canFind(typeOf[l], r))
- cout << 1;
- else cout << 0;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement