oj.uz

Submission #126807

# Submission time Handle Problem Language Result Execution time Memory
126807 2019-07-08T13:00:10 Z zeyad49 Examination (JOI19_examination) Java 11
20 / 100
 1662 ms 58832 KB 
import java.io.*;
import java.util.*;

public class examination {

	static int N=(int)1e5+5;
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner();
		PrintWriter out = new PrintWriter(System.out);
		int n=sc.nextInt(),q=sc.nextInt(),s[]=new int [n],t[]=new int [n],ans[]=new int [q];
		Integer[]indices=new Integer[n];
		for(int i=0;i<n;i++) {
			indices[i]=i;
			s[i]=sc.nextInt();
			t[i]=sc.nextInt();
		}
		Arrays.sort(indices,Comparator.comparingInt(i->-s[i]));
		query[]queries=new query[q];
		for(int i=0;i<q;i++)
			queries[i]=new query(sc.nextInt(),sc.nextInt(),sc.nextInt(),i);
		Arrays.sort(queries,(x,y)->y.a-x.a);
		int student=0;
		FenwickTree ft=new FenwickTree();
		for(query query:queries) {
			while(student<n && s[indices[student]]>=query.a) {
				ft.update(t[indices[student++]],1);
			}
			ans[query.idx]=ft.query(query.b);
		}
		for(int x:ans)
			out.println(x);
		out.close();

	}
	static class FenwickTree
	{
		int []bit;
		FenwickTree(){
			bit=new int [N];
		}
		void update(int idx,int v) {
			idx++;
			while(idx>0) {
				bit[idx]+=v;
				idx-=idx&-idx;
			}
		}
		int query(int idx) {
			idx++;
			int ans=0;
			while(idx<bit.length) {
				ans+=bit[idx];
				idx+=idx&-idx;
			}
			return ans;
		}
	}
	static class query {
		int a,b,c,idx;
		query(int A,int B,int C,int i){
			a=A;
			b=B;
			c=C;
			idx=i;
		}
	}
	static class Scanner {
		BufferedReader br;
		StringTokenizer st;

		Scanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		Scanner(String fileName) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(fileName));
		}

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

		String nextLine() throws IOException {
			return br.readLine();
		}

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

		long nextLong() throws NumberFormatException, IOException {
			return Long.parseLong(next());
		}

		double nextDouble() throws NumberFormatException, IOException {
			return Double.parseDouble(next());
		}

		boolean ready() throws IOException {
			return br.ready();
		}

	}

}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 265 ms 16848 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1609 ms 57048 KB Output is correct
2 Correct 1564 ms 57820 KB Output is correct
3 Correct 1547 ms 57480 KB Output is correct
4 Correct 1662 ms 57844 KB Output is correct
5 Correct 1263 ms 57580 KB Output is correct
6 Correct 1177 ms 57756 KB Output is correct
7 Correct 1530 ms 57804 KB Output is correct
8 Correct 1601 ms 58068 KB Output is correct
9 Correct 1573 ms 58832 KB Output is correct
10 Correct 827 ms 56964 KB Output is correct
11 Correct 1628 ms 57664 KB Output is correct
12 Correct 859 ms 57196 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1609 ms 57048 KB Output is correct
2 Correct 1564 ms 57820 KB Output is correct
3 Correct 1547 ms 57480 KB Output is correct
4 Correct 1662 ms 57844 KB Output is correct
5 Correct 1263 ms 57580 KB Output is correct
6 Correct 1177 ms 57756 KB Output is correct
7 Correct 1530 ms 57804 KB Output is correct
8 Correct 1601 ms 58068 KB Output is correct
9 Correct 1573 ms 58832 KB Output is correct
10 Correct 827 ms 56964 KB Output is correct
11 Correct 1628 ms 57664 KB Output is correct
12 Correct 859 ms 57196 KB Output is correct
13 Incorrect 1590 ms 56828 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 265 ms 16848 KB Output isn't correct
2 Halted 0 ms 0 KB -