結果
問題 | No.1778 括弧列クエリ / Bracketed Sequence Query |
ユーザー |
![]() |
提出日時 | 2022-01-27 20:46:38 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 412 ms / 2,000 ms |
コード長 | 4,909 bytes |
コンパイル時間 | 1,551 ms |
コンパイル使用メモリ | 127,592 KB |
最終ジャッジ日時 | 2025-01-27 15:44:45 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 27 |
ソースコード
#include<iostream>#include<array>#include<string>#include<cstdio>#include<vector>#include<cmath>#include<algorithm>#include<functional>#include<iomanip>#include<queue>#include<ciso646>#include<random>#include<map>#include<set>#include<complex>#include<bitset>#include<stack>#include<unordered_map>#include<utility>#include<tuple>#include<cassert>using namespace std;typedef long long ll;const ll mod = 1000000007;const ll INF = (ll)1000000007 * 1000000007;typedef pair<int, int> P;#define rep(i,n) for(int i=0;i<n;i++)#define per(i,n) for(int i=n-1;i>=0;i--)#define Rep(i,sta,n) for(int i=sta;i<n;i++)#define Per(i,sta,n) for(int i=n-1;i>=sta;i--)typedef long double ld;const ld eps = 1e-8;const ld pi = acos(-1.0);typedef pair<ll, ll> LP;int dx[4]={1,-1,0,0};int dy[4]={0,0,1,-1};template<class T>bool chmax(T &a, const T &b) {if(a<b){a=b;return 1;}return 0;}template<class T>bool chmin(T &a, const T &b) {if(b<a){a=b;return 1;}return 0;}template <class S, S (*op)(S, S), S (*e)()> struct SegmentTree {public:SegmentTree() : SegmentTree(0) {}SegmentTree(int n) : SegmentTree(std::vector<S>(n, e())) {}SegmentTree(const std::vector<S>& v) : _n(int(v.size())) {log = ceil_pow2(_n);size = 1 << log;d = std::vector<S>(2 * size, e());for (int i = 0; i < _n; i++) d[size + i] = v[i];for (int i = size - 1; i >= 1; i--) {update(i);}}void set_val(int p, S x) {assert(0 <= p && p < _n);p += size;d[p] = x;for (int i = 1; i <= log; i++) update(p >> i);}S get(int p) {assert(0 <= p && p < _n);return d[p + size];}S query(int l, int r) {assert(0 <= l && l <= r && r <= _n);S sml = e(), smr = e();l += size;r += size;while (l < r) {if (l & 1) sml = op(sml, d[l++]);if (r & 1) smr = op(d[--r], smr);l >>= 1;r >>= 1;}return op(sml, smr);}S all_query() { return d[1]; }template <bool (*f)(S)> int max_right(int l) {//f(op([l,r)))==trueを満たす最大のrreturn max_right(l, [](S x) { return f(x); });}template <class F> int max_right(int l, F f) {assert(0 <= l && l <= _n);assert(f(e()));if (l == _n) return _n;l += size;S sm = e();do {while (l % 2 == 0) l >>= 1;if (!f(op(sm, d[l]))) {while (l < size) {l = (2 * l);if (f(op(sm, d[l]))) {sm = op(sm, d[l]);l++;}}return l - size;}sm = op(sm, d[l]);l++;} while ((l & -l) != l);return _n;}template <bool (*f)(S)> int min_left(int r) {//f(op([l,r)))==trueを満たす最小のlreturn min_left(r, [](S x) { return f(x); });}template <class F> int min_left(int r, F f) {assert(0 <= r && r <= _n);assert(f(e()));if (r == 0) return 0;r += size;S sm = e();do {r--;while (r > 1 && (r % 2)) r >>= 1;if (!f(op(d[r], sm))) {while (r < size) {r = (2 * r + 1);if (f(op(d[r], sm))) {sm = op(d[r], sm);r--;}}return r + 1 - size;}sm = op(d[r], sm);} while ((r & -r) != r);return 0;}private:int _n, size, log;std::vector<S> d;void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }int ceil_pow2(int n) {int x = 0;while ((1U << x) < (unsigned int)(n)) x++;return x;}};int n,q;string S;vector<int> a;int F(int a,int b){return max(a,b);}int e(){return -mod;}void solve(){cin >> n >> q;cin >> S;vector<int> v;a.resize(n);rep(i,n){if(S[i]=='(') v.push_back(i);else{//cout << v.back() << endl;a[v.back()]=i;a[i]=v.back();v.pop_back();}}//rep(i,n) cout << a[i] << " ";//cout << "" << endl;SegmentTree<int,F,e> seg(a);rep(i,q){int x,y;cin >> x >> y;x--;y--;int v=a[x],w=a[y];int l=min(min(x,y),min(v,w)),r=max(max(x,y),max(v,w));auto check=[&](int x){return x<r;};int ans=seg.min_left(l+1,check);if(ans==0){cout << -1 << endl;continue;}cout << ans << " " << a[ans-1]+1 << endl;}}int main(){ios::sync_with_stdio(false);cin.tie(0);cout << fixed << setprecision(50);solve();}