oj.uz

Submission #708675

# Submission time Handle Problem Language Result Execution time Memory
708675 2023-03-12T07:05:54 Z r1cky Abracadabra (CEOI22_abracadabra) Java 11
10 / 100
 3000 ms 69768 KB 
/*
 * Author: rickytsung
 * Date: 2023/2/9
 * Problem: ABC 256 Ex
 */

import java.util.*;
import java.time.*;
import java.io.*;
import java.math.*;
public class Main{
	public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
	public static long ret,cnt;
	public static int reti,rd,n,m,ans;
	public static boolean neg,b1,b2,b3;
	public static final int mod=998244353,mox=998244352,mod2=1_000_000_007,ma=200005;
	public static Useful us=new Useful(mod);
	public static int[] A=new int[ma];
	public static int[] B=new int[ma];
	public static long[] Al=new long[ma];
	public static long[] Bl=new long[ma];
	public static ArrayList<ArrayList<Integer>> E=new ArrayList<>();
	public static void main(String[] args) throws Exception{
		final int n=readint();
		final int q=readint();
		int[][] C=new int[2][n];
		for(int i=0;i<n;i++) {
			C[0][i]=readint();
		}
		ooo[] Q=new ooo[q];
		int[] ans=new int[q];
		final int max=100000;
		for(int i=0;i<q;i++) {
			Q[i]=new ooo(i,Math.min(max-1,readint()),readint());
		}
		Arrays.sort(Q,new Comparator<ooo>() {
			public int compare(ooo f,ooo s) {
				return f.y-s.y;
			}
		});
		
		int p=0,cnt=0;
		for(int t=0;t<=max;t++) {
			while(cnt<q&&Q[cnt].y==t) {
				ans[Q[cnt].x]=C[p][Q[cnt].z-1];
				cnt++;
			}
			if(cnt==q)break;
			int idx=(n>>1),j=0;
			for(int i=0;i<(n>>1);i++,j++) {
				if(idx==n||C[p][i]<C[p][idx]) {
					C[p^1][j]=C[p][i];
				}
				else {
					i--;
					C[p^1][j]=C[p][idx];
					idx++;
				}
			}
			for(;idx<n;idx++,j++) {
				C[p^1][j]=C[p][idx];
			}
			p^=1;
		}
		for(int i=0;i<q;i++) {
			bw.write(ans[i]+"\n");
		}
		bw.flush();
	}
	
	public static int[] explode(int[] C) {
		final int n=C.length;
		int[] D=new int[n];
		int idx=(n>>1),j=0;
		for(int i=0;i<(n>>1);i++,j++) {
			if(idx==n||C[i]<C[idx]) {
				D[j]=C[i];
			}
			else {
				i--;
				D[j]=C[idx];
				idx++;
			}
		}
		for(;idx<n;idx++,j++) {
			D[j]=C[idx];
		}
		return D;
	}
/*

 */
	public static int readint() throws Exception{
		reti=0;
		neg=false;
		while(rd<48||rd>57) {
			rd=br.read();
			if(rd=='-') {
				neg=true;
			}
		}
		while(rd>47&&rd<58) {
			reti*=10;
			reti+=(rd&15);
			rd=br.read();
		}
		if(neg)reti*=-1;
		return reti;
	}
	
	public static long readlong() throws Exception{
		ret=0;
		neg=false;
		while(rd<48||rd>57) {
			rd=br.read();
			if(rd=='-') {
				neg=true;
			}
		}
		while(rd>47&&rd<58) {
			ret*=10;
			ret+=(rd&15);
			rd=br.read();
		}
		if(neg)ret*=-1;
		return ret;
	}
	
	public static int pint(String in) {
		return Integer.parseInt(in);
	}
	
	public static long plong(String in) {
		return Long.parseLong(in);
	}
	
	public static void outn() {
		System.out.println();
	}
	
	public static void outn(long in) {
		System.out.println(in);
	}
	
	public static void outn(boolean in) {
		System.out.println(in);
	}
	
	public static void outn(String in) {
		System.out.println(in);
	}
	
	public static void out(long in) {
		System.out.print(in);
	}
	
	public static void out(boolean in) {
		System.out.print(in);
	}
	
	public static void out(String in) {
		System.out.print(in);
	}
}

/*

 */
 
/*
 
 */
class ooo{
	int x,y,z;
	ooo(int a,int b,int c){
		x=a;
		y=b;
		z=c;
	}
	
}

class Pii{
	int x,y;
	Pii(int a,int b){
		x=a;
		y=b;
	}
	@Override
    public boolean equals(Object o) {
        if (this==o) return true;
        if (!(o instanceof Pii)) return false;
        Pii key = (Pii) o;
        return x==key.x&&y==key.y;
    }

    @Override
    public int hashCode() {
        long result=x;
        result=31*result+y;
        return (int)(result%998244353);
    }
}

class Pll{
	long x,y;
	Pll(long a,long b){
		x=a;
		y=b;
	}
	
	@Override
    public boolean equals(Object o) {
        if (this==o) return true;
        if (!(o instanceof Pll)) return false;
        Pll key = (Pll) o;
        return x==key.x&&y==key.y;
    }

    @Override
    public int hashCode() {
        long result=x;
        result=31*result+y;
        return (int)(result%998244353);
    }
}

class Useful{
	long mod;
	Useful(long m){mod=m;}
	void al(ArrayList<ArrayList<Integer>> a,int n){for(int i=0;i<n;i++) {a.add(new ArrayList<Integer>());}}
	void arr(int[] a,int init) {for(int i=0;i<a.length;i++) {a[i]=init;}}
	void arr(long[] a,long init) {for(int i=0;i<a.length;i++) {a[i]=init;}}
	void arr(int[][] a,int init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {a[i][j]=init;}}}
	void arr(long[][] a,long init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {a[i][j]=init;}}}
	void arr(int[][][] a,int init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {for(int k=0;k<a[i][j].length;k++) {a[i][j][k]=init;}}}}
	void arr(long[][][] a,long init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {for(int k=0;k<a[i][j].length;k++) {a[i][j][k]=init;}}}}
	void arr(int[][][][] a,int init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {for(int k=0;k<a[i][j].length;k++) {Arrays.fill(a[i][j][k],init);}}}}
	void arr(long[][][][] a,long init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {for(int k=0;k<a[i][j].length;k++) {Arrays.fill(a[i][j][k],init);}}}}
	long fast(long x,long pw) {
		if(pw<=0)return 1;
		if(pw==1)return x;
		long h=fast(x,pw>>1);
		if((pw&1)==0) {
			return h*h%mod;
		}
		return h*h%mod*x%mod;
	}
	long[][] mul(long[][] a,long[][] b){
		long[][] c=new long[a.length][b[0].length];
		for(int i=0;i<a.length;i++) {
			for(int j=0;j<b[0].length;j++) {
				for(int k=0;k<a[0].length;k++) {
					c[i][j]+=a[i][k]*b[k][j];
					c[i][j]%=mod;
				}
			}
		}
		return c;
	}
 
	long[][] fast(long[][] x,int pw){
		if(pw==1)return x;
		long[][] h=fast(x,pw>>1);
		if((pw&1)==0) {
			return mul(h,h);
		}
		else {
			return mul(mul(h,h),x);
		}
	}
	int gcd(int a,int b) {
		if(a==0)return b;
		if(b==0)return a;
		return gcd(b,a%b);
	}
	long gcd(long a,long b) {
		if(a==0)return b;
		if(b==0)return a;
		return gcd(b,a%b);
	}
	long lcm(long a, long b){
	    return a*(b/gcd(a,b));
	}
	double log2(int x) {
		return (Math.log(x)/Math.log(2));
	}
	double log2(long x) {
		return (Math.log(x)/Math.log(2));
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2226 ms 69700 KB Output is correct
2 Correct 2165 ms 69104 KB Output is correct
3 Correct 2167 ms 67984 KB Output is correct
4 Correct 1857 ms 68140 KB Output is correct
5 Correct 2060 ms 69576 KB Output is correct
6 Correct 2192 ms 68508 KB Output is correct
7 Correct 2138 ms 69448 KB Output is correct
8 Correct 2102 ms 68916 KB Output is correct
9 Correct 1961 ms 68332 KB Output is correct
10 Correct 1965 ms 69096 KB Output is correct
11 Correct 2204 ms 68904 KB Output is correct
12 Correct 1921 ms 68296 KB Output is correct
13 Correct 1935 ms 69400 KB Output is correct
14 Correct 2081 ms 69768 KB Output is correct
15 Correct 1952 ms 68896 KB Output is correct
16 Correct 97 ms 14256 KB Output is correct
17 Correct 984 ms 67964 KB Output is correct
18 Correct 1540 ms 68432 KB Output is correct
19 Correct 103 ms 14236 KB Output is correct
20 Correct 100 ms 14100 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3097 ms 58772 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3062 ms 25600 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2226 ms 69700 KB Output is correct
2 Correct 2165 ms 69104 KB Output is correct
3 Correct 2167 ms 67984 KB Output is correct
4 Correct 1857 ms 68140 KB Output is correct
5 Correct 2060 ms 69576 KB Output is correct
6 Correct 2192 ms 68508 KB Output is correct
7 Correct 2138 ms 69448 KB Output is correct
8 Correct 2102 ms 68916 KB Output is correct
9 Correct 1961 ms 68332 KB Output is correct
10 Correct 1965 ms 69096 KB Output is correct
11 Correct 2204 ms 68904 KB Output is correct
12 Correct 1921 ms 68296 KB Output is correct
13 Correct 1935 ms 69400 KB Output is correct
14 Correct 2081 ms 69768 KB Output is correct
15 Correct 1952 ms 68896 KB Output is correct
16 Correct 97 ms 14256 KB Output is correct
17 Correct 984 ms 67964 KB Output is correct
18 Correct 1540 ms 68432 KB Output is correct
19 Correct 103 ms 14236 KB Output is correct
20 Correct 100 ms 14100 KB Output is correct
21 Execution timed out 3097 ms 58772 KB Time limit exceeded
22 Halted 0 ms 0 KB -