Submission #1026958

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026958		ezdp	Abracadabra (CEOI22_abracadabra)	C++14	10 / 100	3064 ms	27984 KiB

Main

#include<bits/stdc++.h>
#define endl '\n'
#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(){
	vector<int> v;
	vector<int> lft, rgt;
	for(int i = 1; i <= n; i ++){
		(i <= n / 2 ? lft : rgt).push_back(a[i]);
	}
	for(int i = 0, j = 0; v.size() < n; ){
		if(i == n / 2) v.push_back(rgt[j ++]);
		else if(j == n / 2) v.push_back(lft[i ++]);
		else if(lft[i] < rgt[j]){
			v.push_back(lft[i ++]);
		}
		else{
			v.push_back(rgt[j ++]);
		}
	}
	bool flag = false;
	for(int i = 1; i <= n; i ++){
		if(a[i] != v[i - 1]) flag = true;
		a[i] = v[i - 1];
	}
	return flag;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(NULL); cout.tie(NULL);
	cin >> n >> q;
	for(int i = 1; i <= n; i ++){
		cin >> a[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;
		}
		ans[idx] = a[x];
	}
	for(int i = 0; i < q; i ++){
		cout << ans[i] << endl;
	}
}
/*

*/

Compilation message (stderr)

Main.cpp: In constructor 'Treap::Node::Node(std::array<int, 3>)':
Main.cpp:20:14: warning: 'Treap::Node::rc' will be initialized after [-Wreorder]
   20 |   Node *lc, *rc;
      |              ^~
Main.cpp:18:7: warning:   'int Treap::Node::my_size' [-Wreorder]
   18 |   int my_size, acc_size;
      |       ^~~~~~~
Main.cpp:22:3: warning:   when initialized here [-Wreorder]
   22 |   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:31:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |    auto [lt, rt] = split(node -> rc, key);
      |         ^
Main.cpp:37:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   37 |    auto [lt, rt] = split(node -> lc, key);
      |         ^
Main.cpp: In member function 'void Treap::insert(std::array<int, 3>)':
Main.cpp:58:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |   auto [lt, rt] = split(root, key);
      |        ^
Main.cpp: In member function 'void Treap::erase(std::array<int, 3>, std::array<int, 3>)':
Main.cpp:63:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   63 |   auto [lt, mrt] = split(root, low_key);
      |        ^
Main.cpp:64:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   64 |   auto [mt, rt] = split(mrt, high_key);
      |        ^
Main.cpp: In function 'bool riffle_shuffle()':
Main.cpp:104:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  104 |  for(int i = 0, j = 0; v.size() < n; ){
      |                        ~~~~~~~~~^~~
Main.cpp: In function 'int main()':
Main.cpp:136:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  136 |  for(auto [t, x, idx] : queries){
      |           ^

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