Submission #480709

#	Time	Username	Problem	Language	Result	Execution time	Memory
480709		Toinfinity1	Fancy Fence (CEOI20_fancyfence)	Java	100 / 100	519 ms	25808 KiB

fancyfence

import java.io.*;
import java.util.*;

public class fancyfence
{
	static class InputReader {
		BufferedReader reader;
		StringTokenizer tokenizer;
		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream), 32768);
			tokenizer = null;
		}
		String next() { // reads in the next string
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}
		public int nextInt() { // reads in the next int
			return Integer.parseInt(next());
		}
		public long nextLong() { // reads in the next long
			return Long.parseLong(next());
		}
		public double nextDouble() { // reads in the next double
			return Double.parseDouble(next());
			}
		}
	static long m = 1000000007;
	static InputReader r = new InputReader(System.in);
	static PrintWriter pw = new PrintWriter(System.out);
	public static void main(String[] args)
	{
		int n = r.nextInt();
		Stack<Integer> stack = new Stack<Integer>();
		long[] h = new long[n+1]; long[] w = new long[n+1]; long[] total = new long[n+1]; long tot = 0;
		for (int i = 1; i <= n; i ++)
		{
			h[i] = r.nextLong();
		}
		for (int i = 1; i <= n; i ++)
		{
			w[i] = r.nextLong();
		}
		long ans = 0;
		stack.add(0);
		for (int i = 1; i <= n; i ++)
		{
			long remove = 0;
			while (h[stack.peek()] >= h[i])
			{
				int j = stack.pop();
				remove += w[j]; remove%=m;
			}
			long x = ((h[i])*(h[i]+1))/2; x%=m; long y = ((w[i])*(w[i]+1))/2; y%=m;
			tot = total[stack.peek()] + (remove*x)%m;
			tot%=m;
			ans += (tot*w[i])%m; ans%=m;
			ans += (x*y)%m; ans%=m;
			total[i] = tot + (w[i]*x)%m; total[i]%=m;
			w[i] += remove; w[i]%=m;
			stack.add(i);
		}
		pw.println(ans);
		pw.close();
	}
}

• Subtask 1: 0 / 0
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 18 / 18
• Subtask 7: 27 / 27