oj.uz

Submission #299150

# Submission time Handle Problem Language Result Execution time Memory
299150 2020-09-14T14:07:27 Z prime_modulus trapezoid (balkan11_trapezoid) Java 11
0 / 100
 94 ms 10488 KB 
import java.util.*;
import java.io.*;

class Trapezoids {
	public static void main(String[] args) throws IOException {
		setIO("trapezoid");

		int N = ni();
		Trapezoid[] T = new Trapezoid[N];
		//T[i] lies completely on the left of T[j] iff T[i].b < T[j].a && T[i].d < T[j].c
		
		for (int i = 0; i < N; i++) {
			st = nl();
			T[i] = new Trapezoid(ni(st), ni(st), ni(st), ni(st));
		}
		Arrays.sort(T);
		
		/*Trapezoid[] d = new Trapezoid[N+1];
		final int INF = (int) 1e9;
		for (int i = 0; i <= N; i++)
			d[i] = new Trapezoid(INF, INF, INF, INF);
		d[0] = new Trapezoid(-INF, -INF, -INF, -INF);
		
		for (int i = 0; i < N; i++) {
			int j = 0;
			for (int b = (N+1)/2; b >= 1; b /= 2) {
				while (j+b <= N && d[j+b].onLeft(T[i])) j += b;
			}
			d[j+1] = T[i];
		}
		
		int ans = 0;
		while (ans < N && d[ans+1].onLeft(new Trapezoid(INF, INF, INF, INF))) ans++;
		
		out.println(ans);*/
		
		int[] best = new int[N+1];
		int[] count = new int[N+1];
		Arrays.fill(count, 1);
		
		int bestLength = 0, bestCount = 0;
		for (int i = 1; i <= N; i++) {
			for (int j = 0; j < i; j++) {
				if (j == 0 || T[j-1].onLeft(T[i-1])) {
					if (best[i] < 1 + best[j]) {
						best[i] = 1 + best[j];
						count[i] = count[j];
					} else if (best[i] == 1 + best[j]) {
						count[i] += count[j];
					}
				}
			}
			bestLength = Math.max(bestLength, best[i]);
		}
		
		for (int i = 1; i <= N; i++) {
			if (best[i] == bestLength) bestCount += count[i];
		}
		
		out.println(bestLength + " " + bestCount);
		
		f.close();
		out.close();
	}
	
	static class Trapezoid implements Comparable<Trapezoid> {
		int a, b, c, d;
		Trapezoid(int a, int b, int c, int d) {
			this.a = a;
			this.b = b;
			this.c = c;
			this.d = d;
		}
		
		public boolean onLeft(Trapezoid o) {
			return this.b < o.a && this.d < o.c;
		}
		
		public int compareTo(Trapezoid o) {
			return Integer.compare(this.a, o.a);
		}
	}

	static BufferedReader f;
	static PrintWriter out;
	static StringTokenizer st;

	static String rl() throws IOException {
		return f.readLine();
	}

	static int ni(StringTokenizer st) {
		return Integer.parseInt(st.nextToken());
	}

	static long nlg(StringTokenizer st) {
		return Long.parseLong(st.nextToken());
	}

	static int ni() throws IOException {
		return Integer.parseInt(rl());
	}

	static long nlg() throws IOException {
		return Long.parseLong(rl());
	}

	static StringTokenizer nl() throws IOException {
		return new StringTokenizer(rl());
	}

	static int[] nia(int N) throws IOException {
		StringTokenizer st = nl();
		int[] A = new int[N];
		for (int i = 0; i < N; i++)
			A[i] = ni(st);
		return A;
	}

	static void setIn(String s) throws IOException {
		f = new BufferedReader(new FileReader(s));
	}

	static void setOut(String s) throws IOException {
		out = new PrintWriter(new FileWriter(s));
	}

	static void setIn() {
		f = new BufferedReader(new InputStreamReader(System.in));
	}

	static void setOut() {
		out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
	}

	static void setIO(String s) throws IOException {
		setIn(s + ".in");
		setOut(s + ".out");
	}

	static void setIO() {
		setIn();
		setOut();
	}
}

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 91 ms 10480 KB Execution failed because the return code was nonzero
2 Runtime error 89 ms 10480 KB Execution failed because the return code was nonzero
3 Runtime error 94 ms 10400 KB Execution failed because the return code was nonzero
4 Runtime error 90 ms 10488 KB Execution failed because the return code was nonzero
5 Runtime error 88 ms 10488 KB Execution failed because the return code was nonzero
6 Runtime error 83 ms 10360 KB Execution failed because the return code was nonzero
7 Runtime error 85 ms 10380 KB Execution failed because the return code was nonzero
8 Runtime error 84 ms 10488 KB Execution failed because the return code was nonzero
9 Runtime error 88 ms 10444 KB Execution failed because the return code was nonzero
10 Runtime error 82 ms 10364 KB Execution failed because the return code was nonzero
11 Runtime error 86 ms 10232 KB Execution failed because the return code was nonzero
12 Runtime error 85 ms 10228 KB Execution failed because the return code was nonzero
13 Runtime error 83 ms 10360 KB Execution failed because the return code was nonzero
14 Runtime error 86 ms 10232 KB Execution failed because the return code was nonzero
15 Runtime error 84 ms 10488 KB Execution failed because the return code was nonzero
16 Runtime error 89 ms 10484 KB Execution failed because the return code was nonzero
17 Runtime error 82 ms 10376 KB Execution failed because the return code was nonzero
18 Runtime error 84 ms 10232 KB Execution failed because the return code was nonzero
19 Runtime error 87 ms 10360 KB Execution failed because the return code was nonzero
20 Runtime error 86 ms 10232 KB Execution failed because the return code was nonzero