Submission #3790997


Source Code Expand

Copy
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.stream.Stream;

public class Main {

	public static void main(String[] args) throws IOException {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskX solver = new TaskX();
		solver.solve(1, in, out);
		out.close();
	}

	static int INF = 1 << 30;
	static long LINF = 1L << 55;
	static int MOD = 1000000007;
	static int[] mh4 = { 0, -1, 1, 0 };
	static int[] mw4 = { -1, 0, 0, 1 };
	static int[] mh8 = { -1, -1, -1, 0, 0, 1, 1, 1 };
	static int[] mw8 = { -1, 0, 1, -1, 1, -1, 0, 1 };

	static class TaskX {

		int m = 100010;
		@SuppressWarnings("unchecked")
		public void solve(int testNumber, InputReader in, PrintWriter out) {

			int n = in.nextInt();
			int[] a = new int[n+2];
			Arrays.fill(a, 0);
			int ans = 0;
			for (int i = 1; i < n+1; i++) {
				a[i] = in.nextInt();
				if (a[i] >= 1) ans = 1;
			}


			int[] as = a.clone();
			Arrays.sort(as);
			Map<Integer, Integer> map = new TreeMap<>();

			{
				int idx = 0;
				for (int i : as) {
					map.put(i, idx++);
				}
			}

			List<Integer>[] g = new ArrayList[m];
			g = Stream.generate(ArrayList::new).limit(m).toArray(List[]::new);

			for (int i = 1; i < n+1; i++) {
				g[map.get(a[i])].add(i);
			}

			int now = 0;
			for (int i = m-1; i >= 0; i--) {
				for (int idx : g[i]) {
					if (a[idx-1] <= a[idx] && a[idx] > a[idx+1]) now++;
					if (a[idx-1] > a[idx] && a[idx] <= a[idx+1]) now--;
				}
				ans = Math.max(ans, now);
			}

			out.println(ans);
			out.flush();
		}
	}

	static class InputReader {
		BufferedReader in;
		StringTokenizer tok;

		public String nextString() {
			while (!tok.hasMoreTokens()) {
				try {
					tok = new StringTokenizer(in.readLine(), " ");
				} catch (IOException e) {
					throw new InputMismatchException();
				}
			}
			return tok.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(nextString());
		}

		public long nextLong() {
			return Long.parseLong(nextString());
		}

		public double nextDouble() {
			return Double.parseDouble(nextString());
		}

		public int[] nextIntArray(int n) {
			int[] res = new int[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextInt();
			}
			return res;
		}

		public int[] nextIntArrayDec(int n) {
			int[] res = new int[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextInt() - 1;
			}
			return res;
		}

		public int[] nextIntArray1Index(int n) {
			int[] res = new int[n + 1];
			for (int i = 0; i < n; i++) {
				res[i + 1] = nextInt();
			}
			return res;
		}

		public long[] nextLongArray(int n) {
			long[] res = new long[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextLong();
			}
			return res;
		}

		public long[] nextLongArrayDec(int n) {
			long[] res = new long[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextLong() - 1;
			}
			return res;
		}

		public long[] nextLongArray1Index(int n) {
			long[] res = new long[n + 1];
			for (int i = 0; i < n; i++) {
				res[i + 1] = nextLong();
			}
			return res;
		}

		public double[] nextDoubleArray(int n) {
			double[] res = new double[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextDouble();
			}
			return res;
		}

		public InputReader(InputStream inputStream) {
			in = new BufferedReader(new InputStreamReader(inputStream));
			tok = new StringTokenizer("");
		}
	}

}

Submission Info

Submission Time
Task D - 日本沈没 (Japan Sinks)
User tutuz
Language Java8 (OpenJDK 1.8.0)
Score 100
Code Size 3943 Byte
Status
Exec Time 478 ms
Memory 60304 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample-01.txt, sample-02.txt, sample-03.txt
Subtask1 7 / 7 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, sample-01.txt, sample-02.txt, sample-03.txt
Subtask2 8 / 8 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, sample-01.txt, sample-02.txt, sample-03.txt
Subtask3 85 / 85 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 03-01.txt, 03-02.txt, 03-03.txt, 03-04.txt, 03-05.txt, 03-06.txt, 03-07.txt, 03-08.txt, 03-09.txt, 03-10.txt, 03-11.txt, 03-12.txt, 03-13.txt, 03-14.txt, 03-15.txt, 03-16.txt, 03-17.txt, 03-18.txt, 03-19.txt, 03-20.txt, sample-01.txt, sample-02.txt, sample-03.txt
Case Name Status Exec Time Memory
01-01.txt 242 ms 29512 KB
01-02.txt 200 ms 31060 KB
01-03.txt 202 ms 28756 KB
01-04.txt 199 ms 31828 KB
01-05.txt 208 ms 30420 KB
01-06.txt 208 ms 31572 KB
01-07.txt 214 ms 30052 KB
01-08.txt 208 ms 31700 KB
01-09.txt 222 ms 30528 KB
01-10.txt 222 ms 30800 KB
01-11.txt 208 ms 32468 KB
01-12.txt 220 ms 30164 KB
01-13.txt 203 ms 31696 KB
01-14.txt 202 ms 31828 KB
01-15.txt 211 ms 29652 KB
01-16.txt 226 ms 31988 KB
02-01.txt 202 ms 32724 KB
02-02.txt 194 ms 29780 KB
02-03.txt 197 ms 30028 KB
02-04.txt 226 ms 32504 KB
02-05.txt 209 ms 30804 KB
02-06.txt 211 ms 29908 KB
02-07.txt 217 ms 30804 KB
02-08.txt 220 ms 29652 KB
02-09.txt 214 ms 31956 KB
02-10.txt 223 ms 32364 KB
03-01.txt 271 ms 34624 KB
03-02.txt 311 ms 44916 KB
03-03.txt 318 ms 46316 KB
03-04.txt 324 ms 46136 KB
03-05.txt 367 ms 46272 KB
03-06.txt 382 ms 43436 KB
03-07.txt 385 ms 43720 KB
03-08.txt 447 ms 58252 KB
03-09.txt 478 ms 60136 KB
03-10.txt 420 ms 58128 KB
03-11.txt 453 ms 59144 KB
03-12.txt 366 ms 41196 KB
03-13.txt 361 ms 40348 KB
03-14.txt 341 ms 42832 KB
03-15.txt 353 ms 40488 KB
03-16.txt 370 ms 40888 KB
03-17.txt 407 ms 42444 KB
03-18.txt 412 ms 43140 KB
03-19.txt 445 ms 60248 KB
03-20.txt 455 ms 60304 KB
sample-01.txt 196 ms 28884 KB
sample-02.txt 205 ms 29908 KB
sample-03.txt 207 ms 30164 KB