Submission #889571

#	Time	Username	Problem	Language	Result	Execution time	Memory
889571		adiyer	Abracadabra (CEOI22_abracadabra)	C++17	10 / 100	185 ms	41148 KiB

Main

// KCPC - 50.6907
#include <bits/stdc++.h>

#define file(s) freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);
#define adiyer(); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(x) x.begin(), x.end()
#define rs(v) v << 1 | 1, md + 1, r
#define ls(v) v << 1, l, md
#define md ((l + r) >> 1)

#define pb emplace_back
#define elif else if
#define uns unsigned
#define emp empty()
#define nll nullptr
#define S second
#define F first

#define int long long

using namespace std;

typedef long long ll;
typedef long double ldb;
typedef vector < ll > vll;
typedef vector < int > vi;
typedef pair < ll, ll > pll;
typedef pair < int, int > pi;
typedef pair < ldb, ldb > pldb;
typedef vector < pair < ll, ll > > vpll;
typedef vector < pair < int, int > > vpi;

const int N = 1e6 + 11;
const int M = 1e3 + 123;
const int mod = 1e9 + 7;
const int mxlg = 19;
const int K = 20;
const int P = 31;
const ll inf = 1e9 + 10;

//mt19937 rnd(07062006);

int n, q;
int a[N], t[N], k[N];

void output(){
	cin >> n >> q;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i <= q; i++) cin >> t[i] >> k[i];
	if(n <= 1000){
		int s[1003][1003];
		for(int i = 0; i <= n; i++){
			memset(s[i], 0, sizeof(s[i]));
			s[0][i] = a[i];
			s[i][n + 1] = inf;
		}
		for(int i = 1; i <= n; i++){
			int i1 = 1, i2 = n / 2 + 1, id = 1;
			while(id <= n){
				if(s[i - 1][i1] <= s[i - 1][i2] && i1 <= n / 2) s[i][id] = s[i - 1][i1], i1++;
				else if(i2 <= n) s[i][id] = s[i - 1][i2], i2++;
				else s[i][id] = s[i - 1][i1], i1++;
				id++;
			}
		}
		for(int i = 1; i <= q; i++){
			if(t[i] > n) t[i] = n;
			cout << s[t[i]][k[i]] << '\n'; 
		}
	}
}

const bool cases = 0;

signed main(){
//  file("disrupt");
    adiyer();
    int tt = 1;
    if(cases) cin >> tt;
    for(int i = 1; i <= tt; i++){
//      cout << "Case " << i << ":\n";
        output();
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 40
• Subtask 3: 0 / 25
• Subtask 4: 0 / 25