結果
問題 |
No.1778 括弧列クエリ / Bracketed Sequence Query
|
ユーザー |
|
提出日時 | 2021-12-19 18:48:14 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,511 bytes |
コンパイル時間 | 4,125 ms |
コンパイル使用メモリ | 109,312 KB |
実行使用メモリ | 52,804 KB |
最終ジャッジ日時 | 2024-09-15 14:44:33 |
合計ジャッジ時間 | 15,568 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 7 WA * 20 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System; using System.Collections.Generic; using System.Linq; class G { static int[] Read() => Array.ConvertAll(Console.ReadLine().Split(), int.Parse); static (int x, int y) Read2() { var a = Read(); return (a[0], a[1]); } static void Main() => Console.WriteLine(Solve()); static object Solve() { var (n, qc) = Read2(); var s = Console.ReadLine(); var qs = Array.ConvertAll(new bool[qc], _ => Read2()); // 対 var pair = new int[n + 1]; var st = new Stack<int>(); for (int i = 1; i <= n; i++) { if (s[i - 1] == '(') { st.Push(i); } else { var l = st.Pop(); pair[l] = i; pair[i] = l; } } for (int qi = 0; qi < qc; qi++) { var (x, y) = qs[qi]; var xl = Math.Min(x, pair[x]); var xr = Math.Max(x, pair[x]); var yl = Math.Min(y, pair[y]); var yr = Math.Max(y, pair[y]); qs[qi] = (Math.Min(xl, yl), Math.Max(xr, yr)); } var map = Array.ConvertAll(new bool[n + 1], _ => new List<int>()); foreach (var qi in Enumerable.Range(0, qc).OrderBy(qi => qs[qi].x)) { var y = qs[qi].y; map[y].Add(qi); } var r = new (int l, int r)[qc]; for (int i = 1; i <= n; i++) { if (s[i - 1] == '(') continue; foreach (var qi in map[i]) st.Push(qi); while (st.Count > 0) { var qi = st.Peek(); if (pair[i] <= qs[qi].x) { st.Pop(); r[qi] = (pair[i], i); } else { break; } } } return string.Join("\n", r.Select(p => p.l == 0 ? "-1" : $"{p.l} {p.r}")); } }