This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
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();
s[i]=Math.min(s[i], t[i]);
}
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]=student;
}
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();
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |