Submission #359348

#	Time	Username	Problem	Language	Result	Execution time	Memory
359348		JerryLiu06	Zoltan (COCI16_zoltan)	Java	70 / 140	978 ms	65536 KiB

zoltan

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

@SuppressWarnings("unchecked") public class zoltan {
	
	static final int MAXN = 200010; static final long MOD = 1000000007;
	
	static int N; static int[] A = new int[MAXN];
	
	static TreeSet<Integer> X = new TreeSet<Integer>(); 
	static ArrayList<Integer> cX = new ArrayList<Integer>();
	
	static int[] tree1 = new int[4 * MAXN]; static int[] tree2 = new int[4 * MAXN];
	static int[] lis = new int[MAXN]; static int[] lds = new int[MAXN];
	
	static ArrayList<Integer> best = new ArrayList<Integer>();
	
	static int[] id1 = new int[MAXN]; static int[] id2 = new int[MAXN];
	static long[] DP1 = new long[MAXN]; static long[] DP2 = new long[MAXN];
	
	static ArrayList<Integer>[] nodes1 = new ArrayList[MAXN];
	static ArrayList<Integer>[] nodes2 = new ArrayList[MAXN];
	
	static int[] next1 = new int[MAXN]; static int[] next2 = new int[MAXN];
	
	static ArrayList<long[]> sum1 = new ArrayList<long[]>();
	static ArrayList<long[]> sum2 = new ArrayList<long[]>();
		
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
				
		StringTokenizer st = new StringTokenizer(br.readLine()); for (int i = 0; i < N; i++) {
			A[i] = Integer.parseInt(st.nextToken()); X.add(A[i]);
		}
		for (int i : X) cX.add(i); for (int i = 0; i < N; i++) A[i] = compress(A[i]);
		
		int max = 0; for (int i = N - 1; i >= 0; i--) {
			lis[i] = queryMax(tree1, 1, 1, N, A[i] + 1, N) + 1; updateMax(tree1, 1, 1, N, A[i], lis[i]);
			lds[i] = queryMax(tree2, 1, 1, N, 1, A[i] - 1) + 1; updateMax(tree2, 1, 1, N, A[i], lds[i]);
			
			max = Math.max(max, lis[i] + lds[i] - 1);
		}
		for (int i = 0; i < N; i++) if (lis[i] + lds[i] - 1 == max) best.add(i);
		
		for (int i = 0; i <= N; i++) nodes1[i] = new ArrayList<Integer>();
		
		for (int i = N - 1; i >= 0; i--) { id1[i] = nodes1[lis[i]].size(); nodes1[lis[i]].add(A[i]); }
		
		for (int i = 0; i <= N; i++) sum1.add(new long[4 * nodes1[i].size()]);
		
		for (int i = N - 1; i >= 0; i--) {
			if (lis[i] == 1) { DP1[i] = 1; updateSum(sum1.get(lis[i]), 1, 0, nodes1[lis[i]].size() - 1, id1[i], 1); continue; }
			
			while (next1[lis[i]] < nodes1[lis[i] - 1].size() && A[i] > nodes1[lis[i] - 1].get(next1[lis[i]])) {
				next1[lis[i]]++;
			}
			long cur = querySum(sum1.get(lis[i] - 1), 1, 0, nodes1[lis[i] - 1].size() - 1, next1[lis[i]], nodes1[lis[i] - 1].size() - 1);
			
			DP1[i] = cur % MOD; updateSum(sum1.get(lis[i]), 1, 0, nodes1[lis[i]].size() - 1, id1[i], DP1[i]);
		}
		for (int i = 0; i <= N; i++) nodes2[i] = new ArrayList<Integer>();
		
		for (int i = N - 1; i >= 0; i--) { id2[i] = nodes2[lds[i]].size(); nodes2[lds[i]].add(A[i]); }
		
		for (int i = 0; i <= N; i++) sum2.add(new long[4 * nodes2[i].size()]);
		
		for (int i = N - 1; i >= 0; i--) {
			if (lds[i] == 1) { DP2[i] = 1; updateSum(sum2.get(lds[i]), 1, 0, nodes2[lds[i]].size() - 1, id2[i], 1); continue; }
			
			while (next2[lds[i]] < nodes2[lds[i] - 1].size() && A[i] < nodes2[lds[i] - 1].get(next2[lds[i]])) {
				next2[lds[i]]++;
			}
			long cur = querySum(sum2.get(lds[i] - 1), 1, 0, nodes2[lds[i] - 1].size() - 1, next2[lds[i]], nodes2[lds[i] - 1].size() - 1);
			
			DP2[i] = cur % MOD; updateSum(sum2.get(lds[i]), 1, 0, nodes2[lds[i]].size() - 1, id2[i], DP2[i]);
		}
		long ans = 0; for (int i : best) { ans += DP1[i] * DP2[i]; ans %= MOD; }
		
		ans *= exp(2, N - max); ans %= MOD; System.out.println(max + " " + ans);
	}
	static void updateMax(int[] tree, int x, int l, int r, int pos, int val) { int mid = (l + r) / 2;
		if (pos < l || pos > r) return ; if (l == r) { tree[x] = val; return ; }
		
		updateMax(tree, 2 * x, l, mid, pos, val); updateMax(tree, 2 * x + 1, mid + 1, r, pos, val); 
		tree[x] = Math.max(tree[2 * x], tree[2 * x + 1]);
	}
	static int queryMax(int[] tree, int x, int l, int r, int tl, int tr) { int mid = (l + r) / 2;
		if (r < tl || l > tr) return 0; if (tl <= l && r <= tr) return tree[x];
		
		return Math.max(queryMax(tree, 2 * x, l, mid, tl, tr), queryMax(tree, 2 * x + 1, mid + 1, r, tl, tr));
	}
	static void updateSum(long[] tree, int x, int l, int r, int pos, long val) { int mid = (l + r) / 2; 
		if (pos < l || pos > r) return ; if (l == r) { tree[x] = val; return ; }
		
		updateSum(tree, 2 * x, l, mid, pos, val); updateSum(tree, 2 * x + 1, mid + 1, r, pos, val);
		tree[x] = tree[2 * x] + tree[2 * x + 1];
	}
	static long querySum(long[] tree, int x, int l, int r, int tl, int tr) { int mid = (l + r) / 2;
		if (r < tl || l > tr) return 0; if (tl <= l && r <= tr) return tree[x];
		
		return querySum(tree, 2 * x, l, mid, tl, tr) + querySum(tree, 2 * x + 1, mid + 1, r, tl, tr);
	}
	static int compress(int val) {
		int low = 0; int high = cX.size() - 1; int res = 0;
		
		while (low <= high) { int mid = (low + high) / 2;
			if (cX.get(mid) >= val) { res = mid; high = mid - 1; } else low = mid + 1;
		}
		return res + 1;
	}
	static long exp(long base, int pow) {
		if (pow == 0) return 1; if (pow == 1) return (base + MOD) % MOD;
		
		long res = exp(base, pow / 2); res = (res * res + MOD) % MOD;
		if (pow % 2 == 1) res = (res * base + MOD) % MOD;
		
		return (res + MOD) % MOD;
	}
}

• Subtask 1: 70 / 140