Submission #3783270


Source Code Expand

Copy
using System;
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 r, char o, Node l)
	{
		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 a = G;
		var leaves = new List<Node>();
		var e = Parse(S, a, 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 - a[b] + MOD) * leaves[b].Diff) % MOD);
		}
		Out.Flush();
	}
	Node Parse(string S, int[] a, List<Node> leaves)
	{
		int id = 0;
		var ops = new Stack<char>();
		var nodes = new Stack<Node>();
		Action<Func<bool>> f = p => { while (p()) nodes.Push(new OpNode(nodes.Pop(), ops.Pop(), nodes.Pop())); };
		foreach (var c in S)
		{
			switch (c)
			{
				case 'a':
					var v = new VarNode(id, a[id++]); leaves.Add(v); nodes.Push(v);
					break;
				case '(':
				case '*':
					ops.Push(c);
					break;
				case ')':
					f(() => ops.Peek() != '(');
					ops.Pop();
					break;
				default:
					f(() => ops.Count > 0 && ops.Peek() != '(');
					ops.Push(c);
					break;
			}
		}
		f(() => ops.Count > 0);
		return nodes.Pop();
	}
}

Submission Info

Submission Time
Task E - 数式とクエリ
User selpo
Language C# (Mono 4.6.2.0)
Score 700
Code Size 2350 Byte
Status
Exec Time 317 ms
Memory 37848 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 27 ms 11476 KB
02.txt 27 ms 11476 KB
11.txt 313 ms 35356 KB
12.txt 317 ms 33340 KB
13.txt 303 ms 31296 KB
14.txt 315 ms 35776 KB
15.txt 314 ms 33852 KB
16.txt 293 ms 36432 KB
17.txt 258 ms 34644 KB
18.txt 215 ms 17580 KB
19.txt 217 ms 17580 KB
20.txt 213 ms 17580 KB
21.txt 215 ms 21676 KB
22.txt 217 ms 19628 KB
23.txt 162 ms 16704 KB
24.txt 177 ms 14652 KB
25.txt 316 ms 35928 KB
26.txt 305 ms 33880 KB
27.txt 272 ms 37848 KB
28.txt 262 ms 31828 KB
29.txt 211 ms 19632 KB
30.txt 273 ms 32428 KB
31.txt 267 ms 30120 KB
32.txt 274 ms 29996 KB
33.txt 271 ms 30120 KB
34.txt 270 ms 30120 KB
35.txt 209 ms 29120 KB
36.txt 198 ms 29380 KB
37.txt 280 ms 32168 KB
38.txt 280 ms 34212 KB
39.txt 268 ms 28068 KB
40.txt 241 ms 29996 KB
41.txt 237 ms 25776 KB
42.txt 77 ms 30672 KB
43.txt 76 ms 26704 KB
44.txt 77 ms 32720 KB
45.txt 67 ms 26832 KB
46.txt 67 ms 26704 KB
47.txt 77 ms 31444 KB
48.txt 76 ms 28116 KB
49.txt 76 ms 26068 KB
50.txt 79 ms 27860 KB
51.txt 76 ms 27860 KB
52.txt 66 ms 24020 KB
53.txt 67 ms 26836 KB