Submission #126807

#	Time	Username	Problem	Language	Result	Execution time	Memory
126807		zeyad49	Examination (JOI19_examination)	Java	20 / 100	1662 ms	58832 KiB

examination

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
• Subtask 2: 20 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57