Vlad_Zhukov's blog

By Vlad_Zhukov, 12 years ago, In Russian

Уже несколько месяцев учу Java, но так и не могу научиться понимать какие задачи ей решить нельзя из-за времени работы. Вот условия задачи: http://informatics.mccme.ru/moodle/mod/statements/view3.php?id=1041&chapterid=1338#1 Решил все по разбору(он есть там же по ссылке), с асимптотикой все ок. Сделал вывод, что это из-за времени работы java.

Т_ак можно ли как-то ускорить мое решение, чтобы оно зашло или все-таки писать на другом языке?_

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;



public class NGU_Building {	
	class Event{
		int type, area, z;
		Event(int t, int s, int pos){
			type = t;
		    area = s;
		    z = pos;
		}
	}
	
	class SortByZ implements Comparator<Event>{

		@Override
		public int compare(Event a, Event b) {
			if (a.z > b.z)
				return 1;
			else
				if (a.z < b.z)
					return -1;
				else
					if (a.type < b.type)
						return 1;
					else
						if(a.type > b.type)
							return -1;
						else
							return 0;
		}
		
	}

	BufferedReader in;
	PrintWriter out;
	StringTokenizer st;
	final int MaxN = 200000;
	
	void solve() throws IOException {
		int n = nextInt();
		int w = nextInt();
		int l = nextInt();
		Event[] events = new Event[2 * n];
		Event[] events1 = new Event[2 * n];
		for (int i = 0; i < n; i++){
			int x1 = nextInt();
			int y1 = nextInt();
			int z1 = nextInt();
			int x2 = nextInt();
			int y2 = nextInt();
			int z2 = nextInt();
			int area = (x2 - x1) * (y2 - y1);
			events[2 * i] = new Event(0, area, z1);
			events[2 * i + 1] = new Event(1, area, z2);
			events1[2 * i] = new Event(0, area, z1);
			events1[2 * i + 1] = new Event(1, area, z2);
		}
		Arrays.sort(events, new SortByZ());
		int s = 0;
		int k = 0;
		int mink = MaxN;
		int minz = -1;
		for (Event i: events){
			if (i.type == 0){
				s += i.area;
				k++;
			}
			else{
				s -= i.area;
				k--;
			}
			if (s == w * l){
				if (k < mink){
					mink = k;
					minz = i.z;
				}
			}
		}
		if (minz == -1){
			out.println("NO");
			return;
		}
		out.println("YES");
		out.println(mink);
		
		for (int i = 0; i < n; i++){
			if (events1[2 * i].z <= minz && events1[2 * i + 1].z > minz)
				out.println(i + 1);
		}
	}

	void run() throws IOException {
		in = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(new OutputStreamWriter(System.out));

		solve();

		in.close();
		out.close();
	}

	public static void main(String[] args) throws IOException {
		new NGU_Building().run();
	}

	String nextToken() throws IOException {
		while (st == null || !st.hasMoreTokens()) {
			st = new StringTokenizer(in.readLine());
		}
		return st.nextToken();
	}

	int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}

}
  • Vote: I like it
  • +8
  • Vote: I do not like it