Submission #798162

#	Time	Username	Problem	Language	Result	Execution time	Memory
798162		IvanJ	Abracadabra (CEOI22_abracadabra)	C++17	100 / 100	647 ms	63392 KiB

Main

#include<bits/stdc++.h>

#define pb push_back
#define x first
#define y second
#define all(a) (a).begin(), (a).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 2e5 + 5, maxq = 1e6 + 5;

struct Data {
	int v, l, r, id;
	friend bool operator<(Data A, Data B) {
		if(A.v != B.v)
			return A.v < B.v;
		return A.id < B.id;
	}
	int len() {return r - l + 1;}
};

int n, q, m;
int p[maxn];
int ID[maxn * 2];
int nxt[maxn];
int ans[maxq];
vector<ii> qs[maxn];
set<Data> active;
vector<Data> blocks;

struct Seg {
	int pot;
	vector<int> T;
	void init(int sz) {
		pot = 1;
		while(pot < sz) pot <<= 1;
		T = vector<int>((pot << 1), 0);
	}
	
	void update(int x, int v) {
		x += pot;
		T[x] = v, x >>= 1;
		while(x > 0) T[x] = T[x * 2] + T[x * 2 + 1], x >>= 1;
	}
	
	ii query(int x, int lo, int hi, int cnt) {
		if(lo == hi) return {x - pot, cnt};
		int mid = (lo + hi) / 2;
		if(T[x * 2] >= cnt) 
			return query(x * 2, lo, mid, cnt);
		return query(x * 2 + 1, mid + 1, hi, cnt - T[x * 2]);
	}
	
	int get(int x) {
		ii res = query(1, 0, pot - 1, x);
		return p[blocks[res.x].l + res.y - 1];
	}
} S;

void init() {
	int x = 0, idx = 0;
	while(x != n) 
		blocks.pb({p[x], x, nxt[x] - 1, idx++}), x = nxt[x];
}

void build() {
	int sz = n, idx = (int)blocks.size();
	for(Data D : blocks)
		active.insert(D);
	
	int flag = 1;
	while(flag) {
		while(1) {
			auto it = --active.end();
			int len = it->r - it->l + 1;
			if(sz - len >= n / 2) 
				active.erase(it), sz -= len;
			else break;
		}
		
		if(sz == n / 2) flag = 0;
		else {
			auto it = --active.end();
			Data D = *it;
			active.erase(it);
			int nr = D.r - (sz - (n / 2)) + 1;
			Data D1 = {D.v, D.l, nr - 1, idx++};
			active.insert(D1), blocks.pb(D1);
			while(nr <= D.r) {
				int hi = min(nxt[nr] - 1, D.r);
				Data Di = {p[nr], nr, hi, idx++};
				active.insert(Di), blocks.pb(Di);
				nr = hi + 1;
			}
		}
	}
	
	m = (int)blocks.size();
	sort(all(blocks));
	for(int i = 0;i < m;i++) 
		ID[blocks[i].id] = i;
	S.init(m);
}

void solve() {
	int x = 0, idx = 0, sz = n;
	active.clear();
	while(x != n) {
		S.update(ID[idx], nxt[x] - x);
		active.insert({p[x], x, nxt[x] - 1, idx++});
		x = nxt[x];
	}
	
	for(int t = 0;t <= n;t++) {
		for(ii qi : qs[t]) 
			ans[qi.y] = S.get(qi.x);
		
		while(1) {
			auto it = --active.end();
			int len = it->r - it->l + 1;
			if(sz - len >= n / 2) 
				active.erase(it), sz -= len;
			else break;
		}
		
		if(sz > n / 2) {
			auto it = --active.end();
			Data D = *it;
			active.erase(it);
			S.update(ID[D.id], 0);
			int nr = D.r - (sz - (n / 2)) + 1;
			Data D1 = {D.v, D.l, nr - 1, idx++};
			active.insert(D1);
			S.update(ID[D1.id], D1.len());
			while(nr <= D.r) {
				int hi = min(nxt[nr] - 1, D.r);
				Data Di = {p[nr], nr, hi, idx++};
				active.insert(Di);
				S.update(ID[Di.id], Di.len());
				nr = hi + 1;
			}
		}
	}
}

int main() {
	scanf("%d%d", &n, &q);
	for(int i = 0;i < n;i++) 
		scanf("%d", p + i);
	for(int i = 0;i < q;i++) {
		int t, x;
		scanf("%d%d", &t, &x);
		qs[min(t, n)].pb({x, i});
	}
	
	p[n] = n + 1;
	vector<int> v = {n};
	for(int i = n - 1;i >= 0;i--) {
		while(p[i] > p[v.back()]) v.pop_back();
		nxt[i] = v.back(), v.pb(i);
	}
	
	init();
	build();
	memset(ans, -1, sizeof ans);
	solve();
	for(int i = 0;i < q;i++) 
		printf("%d\n", ans[i]);
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:150:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |  scanf("%d%d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:152:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 |   scanf("%d", p + i);
      |   ~~~~~^~~~~~~~~~~~~
Main.cpp:155:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  155 |   scanf("%d%d", &t, &x);
      |   ~~~~~^~~~~~~~~~~~~~~~

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