Submission #3910827


Source Code Expand

Copy
using System.Collections.Generic;
using System.IO;
using System.Linq;
using static System.Console;
class Z { static void Main() => new K(); }
abstract class Node
{
	public long Diff, Value;
	public abstract void GetDiff(long diff);
}
class VarNode : Node
{
	public int Id;
	public VarNode(int id, long val) { Id = id; Value = val; }
	public override void GetDiff(long diff) { Diff = diff; }
}
class OpNode : Node
{
	public char Op;
	public Node Left, Right;
	public OpNode(Node l, char o, Node r)
	{
		Left = l; Op = o; Right = r;
		switch (Op)
		{
			case '+': Value = (Left.Value + Right.Value) % K.MOD; break;
			case '*': Value = Left.Value * Right.Value % K.MOD; break;
			default: Value = (Left.Value - Right.Value + K.MOD) % K.MOD; break;
		}
	}
	public override void GetDiff(long diff)
	{
		Diff = diff;
		switch (Op)
		{
			case '+': Left.GetDiff(diff); Right.GetDiff(diff); break;
			case '*': Left.GetDiff(Right.Value * diff % K.MOD); Right.GetDiff(Left.Value * diff % K.MOD); break;
			default: Left.GetDiff(diff); Right.GetDiff((K.MOD - diff) % K.MOD); break;
		}
	}
}
class K
{
	int[] G => ReadLine().Split().Select(int.Parse).ToArray();
	public const int MOD = 1000000007;
	public K()
	{
		SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
		var S = ReadLine();
		var Q = G[0];
		var leaves = new List<Node>();
		var e = Parse(S, G, leaves);
		e.GetDiff(1);
		for (var i = 0; i < Q; i++)
		{
			var q = G;
			int b = q[0] - 1, x = q[1];
			WriteLine((e.Value + (x - leaves[b].Value + MOD) * leaves[b].Diff) % MOD);
		}
		Out.Flush();
	}
	Node Parse(string S, int[] a, List<Node> leaves)
	{
		var index = 0;
		var Id = 0;
		var N = S.Length;
		var st = new Stack<object>();
		object ret = null;
		st.Push(new E0());
		while (st.Count > 0)
		{
			var f = st.Pop();
			if (f is E0) { st.Push(new E1()); st.Push(new T0()); }
			else if (f is E1)
			{
				var n = (Node)ret;
				st.Push(new E2(n));
			}
			else if (f is E2)
			{
				var e2 = (E2)f;
				if (index < N && (S[index] == '+' || S[index] == '-'))
				{
					var op = S[index];
					index++;
					st.Push(new E3(e2.N, op));
					st.Push(new T0());
				}
				else ret = e2.N;
			}
			else if (f is E3)
			{
				var e3 = (E3)f;
				var m = (Node)ret;
				var n = new OpNode(e3.N, e3.Op, m);
				st.Push(new E2(n));
			}
			else if (f is T0) { st.Push(new T1()); st.Push(new V0()); }
			else if (f is T1)
			{
				var n = (Node)ret;
				st.Push(new T2(n));
			}
			else if (f is T2)
			{
				var t2 = (T2)f;
				if (index < N && S[index] == '*')
				{
					var op = S[index];
					index++;
					st.Push(new T3(t2.N, op));
					st.Push(new V0());
				}
				else ret = t2.N;
			}
			else if (f is T3)
			{
				var t3 = (T3)f;
				var m = (Node)ret;
				var n = new OpNode(t3.N, t3.Op, m);
				st.Push(new T2(n));
			}
			else if (f is V0)
			{
				if (S[index] == '(')
				{
					index++;
					st.Push(new V1());
					st.Push(new E0());
				}
				else
				{
					var x = new VarNode(Id, a[Id++]);
					leaves.Add(x);
					index++;
					ret = x;
				}
			}
			else if (f is V1) index++;
		}
		return (Node)ret;
	}
}
struct E0 { }
struct E1 { }
struct E2 { public Node N; public E2(Node n) { N = n; } }
struct E3 { public Node N; public char Op; public E3(Node n, char op) { N = n; Op = op; } }
struct T0 { }
struct T1 { }
struct T2 { public Node N; public T2(Node n) { N = n; } }
struct T3 { public Node N; public char Op; public T3(Node n, char op) { N = n; Op = op; } }
struct V0 { }
struct V1 { }

Submission Info

Submission Time
Task E - 数式とクエリ
User selpo
Language C# (Mono 4.6.2.0)
Score 700
Code Size 3638 Byte
Status
Exec Time 340 ms
Memory 37968 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 01.txt, 02.txt
All 700 / 700 01.txt, 02.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt, 51.txt, 52.txt, 53.txt
Case Name Status Exec Time Memory
01.txt 29 ms 11604 KB
02.txt 30 ms 13652 KB
11.txt 324 ms 35900 KB
12.txt 332 ms 31420 KB
13.txt 340 ms 31420 KB
14.txt 333 ms 33976 KB
15.txt 336 ms 31932 KB
16.txt 297 ms 36684 KB
17.txt 278 ms 33488 KB
18.txt 249 ms 24232 KB
19.txt 252 ms 22308 KB
20.txt 252 ms 24232 KB
21.txt 253 ms 26280 KB
22.txt 255 ms 24232 KB
23.txt 197 ms 26416 KB
24.txt 215 ms 25520 KB
25.txt 328 ms 31292 KB
26.txt 340 ms 28248 KB
27.txt 292 ms 34000 KB
28.txt 291 ms 37968 KB
29.txt 249 ms 30376 KB
30.txt 314 ms 32460 KB
31.txt 317 ms 34380 KB
32.txt 302 ms 32332 KB
33.txt 306 ms 32332 KB
34.txt 302 ms 30284 KB
35.txt 229 ms 30392 KB
36.txt 240 ms 32436 KB
37.txt 313 ms 32332 KB
38.txt 315 ms 36428 KB
39.txt 314 ms 30284 KB
40.txt 263 ms 31144 KB
41.txt 267 ms 29096 KB
42.txt 104 ms 31180 KB
43.txt 105 ms 31308 KB
44.txt 105 ms 33228 KB
45.txt 92 ms 27212 KB
46.txt 93 ms 31308 KB
47.txt 100 ms 30800 KB
48.txt 104 ms 33740 KB
49.txt 102 ms 33868 KB
50.txt 104 ms 35788 KB
51.txt 104 ms 33740 KB
52.txt 93 ms 31820 KB
53.txt 88 ms 28624 KB