oj.uz

Submission #708674

# Submission time Handle Problem Language Result Execution time Memory
708674 2023-03-12T07:04:25 Z r1cky Abracadabra (CEOI22_abracadabra) Java 11
10 / 100
 2063 ms 83048 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=1000;
		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 2063 ms 69824 KB Output is correct
2 Correct 1878 ms 76604 KB Output is correct
3 Correct 1954 ms 75532 KB Output is correct
4 Correct 1693 ms 74568 KB Output is correct
5 Correct 1880 ms 76564 KB Output is correct
6 Correct 1977 ms 75208 KB Output is correct
7 Correct 1896 ms 76904 KB Output is correct
8 Correct 1893 ms 75276 KB Output is correct
9 Correct 1704 ms 74544 KB Output is correct
10 Correct 1777 ms 75600 KB Output is correct
11 Correct 1927 ms 75564 KB Output is correct
12 Correct 1658 ms 73952 KB Output is correct
13 Correct 1687 ms 75640 KB Output is correct
14 Correct 1834 ms 76604 KB Output is correct
15 Correct 1702 ms 75212 KB Output is correct
16 Correct 97 ms 14112 KB Output is correct
17 Correct 943 ms 73768 KB Output is correct
18 Correct 1243 ms 73996 KB Output is correct
19 Correct 92 ms 14224 KB Output is correct
20 Correct 95 ms 14036 KB Output is correct

Subtask #2
0 / 40.0

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

Subtask #3
0 / 25.0

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

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2063 ms 69824 KB Output is correct
2 Correct 1878 ms 76604 KB Output is correct
3 Correct 1954 ms 75532 KB Output is correct
4 Correct 1693 ms 74568 KB Output is correct
5 Correct 1880 ms 76564 KB Output is correct
6 Correct 1977 ms 75208 KB Output is correct
7 Correct 1896 ms 76904 KB Output is correct
8 Correct 1893 ms 75276 KB Output is correct
9 Correct 1704 ms 74544 KB Output is correct
10 Correct 1777 ms 75600 KB Output is correct
11 Correct 1927 ms 75564 KB Output is correct
12 Correct 1658 ms 73952 KB Output is correct
13 Correct 1687 ms 75640 KB Output is correct
14 Correct 1834 ms 76604 KB Output is correct
15 Correct 1702 ms 75212 KB Output is correct
16 Correct 97 ms 14112 KB Output is correct
17 Correct 943 ms 73768 KB Output is correct
18 Correct 1243 ms 73996 KB Output is correct
19 Correct 92 ms 14224 KB Output is correct
20 Correct 95 ms 14036 KB Output is correct
21 Incorrect 1353 ms 83048 KB Output isn't correct
22 Halted 0 ms 0 KB -