Submission #1026962

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026962		ezdp	Abracadabra (CEOI22_abracadabra)	C++14	100 / 100	1659 ms	56664 KiB

Main

#include<bits/stdc++.h>
#define de(x) cout << #x << " = " << x << endl;
#define all(A) A.begin(), A.end()
using namespace std;

const int MAXN = 2e5;
const int MAXQ = 1e6;

ostream& operator<<(ostream& out, array<int, 3> v){
	out << "(" << v[0] << " " << v[1] << " " << v[2] << ")";
	return out;
}

struct Treap{
	struct Node{
		array<int, 3> val;
		int my_size, acc_size;
		int prior;
		Node *lc, *rc;
		Node() {}
		Node(array<int, 3> val) : val(val), prior(rand()), lc(nullptr), rc(nullptr), my_size(val[2] - val[1] + 1), acc_size(val[2] - val[1] + 1) {}
		void update(){
			acc_size = my_size + (lc == nullptr ? 0 : lc -> acc_size) + (rc == nullptr ? 0 : rc -> acc_size);
		}
	};
	Node* root;
	pair<Node*, Node*> split(Node* node, array<int, 3> key){
		if(node == nullptr) return {nullptr, nullptr};
		if(node -> val <= key){
			auto [lt, rt] = split(node -> rc, key);
			node -> rc = lt;
			node -> update();
			return {node, rt};
		}
		else{
			auto [lt, rt] = split(node -> lc, key);
			node -> lc = rt;
			node -> update();
			return {lt, node};
		}
	}
	Node* merge(Node* lt, Node* rt){
		if(lt == nullptr) return rt;
		if(rt == nullptr) return lt;
		if(lt -> prior < rt -> prior){
			rt -> lc = merge(lt, rt -> lc);
			rt -> update();
			return rt;
		}
		else{
			lt -> rc = merge(lt -> rc, rt);
			lt -> update();
			return lt;
		}
	}
	void insert(array<int, 3> key){
		auto [lt, rt] = split(root, key);
		auto mt = new Node(key);
		root = merge(merge(lt, mt), rt);
	}
	void erase(array<int, 3> low_key, array<int, 3> high_key){
		auto [lt, mrt] = split(root, low_key);
		auto [mt, rt] = split(mrt, high_key);
		root = merge(lt, rt);
	}
	void util_print(Node* node){
		if(node == nullptr) return;
		util_print(node -> lc);
		cout << node -> val << " ";
		util_print(node -> rc);
	}
	void print(){ util_print(root); cout << endl; }
	array<int, 3> util_search(Node* node, int &to_left, int key){
		if(to_left + (node -> lc == nullptr ? 0 : node -> lc -> acc_size) < key && to_left + (node -> lc == nullptr ? 0 : node -> lc -> acc_size) +  (node -> my_size) >= key){
			to_left += (node -> lc == nullptr ? 0 : node -> lc -> acc_size);
			return node -> val;
		}
		else if(to_left + (node -> lc == nullptr ? 0 : node -> lc -> acc_size) < key){
			to_left += (node -> acc_size) - (node -> rc -> acc_size);
			return util_search(node -> rc, to_left, key);
		}
		else{
			return util_search(node -> lc, to_left, key);
		}
	}
	pair<int, array<int, 3>> search(int key){ 
		int shift = 0; 
		auto ret = util_search(root, shift, key);
		return {shift, ret};
	}
};

int n, q, a[MAXN + 5], ans[MAXQ + 5], nxt[MAXN + 5];
vector<array<int, 3>> queries;
Treap tr;

bool riffle_shuffle(){
	auto [shift, block] = tr.search(n / 2);
	// cout << "middle block is " << block << " and previous blocks shift with " << shift << endl;
	if(shift + block[2] - block[1] + 1 == n / 2) return false;
	auto [v, l, r] = block;
	tr.erase({v, 0, 0}, {v + 1, 0, 0});
	tr.insert({v, l, n / 2 - shift + block[1] - 1});
	int m = n / 2 - shift + block[1];
	// de(m);
	while(m > 0 && m <= r){
		int my_r = min(r, nxt[m] - 1);
		tr.insert({a[m], m, my_r});
		// cout << "new block " << m << " " << my_r << endl;
		m = my_r + 1;
	}
	// tr.print();
	return true;
}

int main(){
	cin >> n >> q;
	for(int i = 1; i <= n; i ++){
		cin >> a[i];
	}
	for(int i = 1; i <= n; ){
		int j = i;
		while(j <= n && a[j] <= a[i]){
			++ j;
		}
		tr.insert({a[i], i, j - 1});
		i = j;
	}
	// tr.print();
	stack<int> st;
	for(int i = n; i >= 1; i --){
		while(!st.empty() && a[st.top()] < a[i]){
			st.pop();
		}
		nxt[i] = (st.empty() ? n+1 : st.top());
		st.push(i);
	}
	for(int i = 0; i < q; i ++){
		int x, t; cin >> t >> x;
		queries.push_back({t, x, i});
	}
	sort(all(queries));
	
	int cur_time = 0;
	for(auto [t, x, idx] : queries){
		while(cur_time < t){
			if(riffle_shuffle()) ++ cur_time;
			else cur_time = t;
		}
		// cout << "(" << t << ", " << x << ", " << idx << ") -> "; tr.print(); 
		auto [shift, block] = tr.search(x);
		ans[idx] = a[x - shift + block[1] - 1];
	}
	for(int i = 0; i < q; i ++){
		cout << ans[i] << endl;
	}
}
/*
6 3
1 5 6 2 3 4
1 2
0 4
1 5
*/

Compilation message (stderr)

Main.cpp: In constructor 'Treap::Node::Node(std::array<int, 3>)':
Main.cpp:19:14: warning: 'Treap::Node::rc' will be initialized after [-Wreorder]
   19 |   Node *lc, *rc;
      |              ^~
Main.cpp:17:7: warning:   'int Treap::Node::my_size' [-Wreorder]
   17 |   int my_size, acc_size;
      |       ^~~~~~~
Main.cpp:21:3: warning:   when initialized here [-Wreorder]
   21 |   Node(array<int, 3> val) : val(val), prior(rand()), lc(nullptr), rc(nullptr), my_size(val[2] - val[1] + 1), acc_size(val[2] - val[1] + 1) {}
      |   ^~~~
Main.cpp: In member function 'std::pair<Treap::Node*, Treap::Node*> Treap::split(Treap::Node*, std::array<int, 3>)':
Main.cpp:30:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   30 |    auto [lt, rt] = split(node -> rc, key);
      |         ^
Main.cpp:36:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   36 |    auto [lt, rt] = split(node -> lc, key);
      |         ^
Main.cpp: In member function 'void Treap::insert(std::array<int, 3>)':
Main.cpp:57:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |   auto [lt, rt] = split(root, key);
      |        ^
Main.cpp: In member function 'void Treap::erase(std::array<int, 3>, std::array<int, 3>)':
Main.cpp:62:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   62 |   auto [lt, mrt] = split(root, low_key);
      |        ^
Main.cpp:63:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   63 |   auto [mt, rt] = split(mrt, high_key);
      |        ^
Main.cpp: In function 'bool riffle_shuffle()':
Main.cpp:98:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   98 |  auto [shift, block] = tr.search(n / 2);
      |       ^
Main.cpp:101:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  101 |  auto [v, l, r] = block;
      |       ^
Main.cpp: In function 'int main()':
Main.cpp:145:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  145 |  for(auto [t, x, idx] : queries){
      |           ^
Main.cpp:151:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  151 |   auto [shift, block] = tr.search(x);
      |        ^

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