oj.uz

Submission #1026958

# Submission time Handle Problem Language Result Execution time Memory
1026958 2024-07-18T15:10:08 Z ezdp Abracadabra (CEOI22_abracadabra) C++14
10 / 100
 3000 ms 27984 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 20548 KB Output is correct
2 Correct 398 ms 27984 KB Output is correct
3 Correct 308 ms 27216 KB Output is correct
4 Correct 299 ms 26032 KB Output is correct
5 Correct 342 ms 27568 KB Output is correct
6 Correct 301 ms 26860 KB Output is correct
7 Correct 375 ms 27824 KB Output is correct
8 Correct 332 ms 26628 KB Output is correct
9 Correct 305 ms 25868 KB Output is correct
10 Correct 326 ms 27052 KB Output is correct
11 Correct 328 ms 26812 KB Output is correct
12 Correct 319 ms 26156 KB Output is correct
13 Correct 322 ms 26288 KB Output is correct
14 Correct 396 ms 27056 KB Output is correct
15 Correct 357 ms 26836 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 340 ms 25524 KB Output is correct
18 Correct 365 ms 25636 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 1 ms 2396 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3064 ms 15836 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3062 ms 5588 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 20548 KB Output is correct
2 Correct 398 ms 27984 KB Output is correct
3 Correct 308 ms 27216 KB Output is correct
4 Correct 299 ms 26032 KB Output is correct
5 Correct 342 ms 27568 KB Output is correct
6 Correct 301 ms 26860 KB Output is correct
7 Correct 375 ms 27824 KB Output is correct
8 Correct 332 ms 26628 KB Output is correct
9 Correct 305 ms 25868 KB Output is correct
10 Correct 326 ms 27052 KB Output is correct
11 Correct 328 ms 26812 KB Output is correct
12 Correct 319 ms 26156 KB Output is correct
13 Correct 322 ms 26288 KB Output is correct
14 Correct 396 ms 27056 KB Output is correct
15 Correct 357 ms 26836 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 340 ms 25524 KB Output is correct
18 Correct 365 ms 25636 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 1 ms 2396 KB Output is correct
21 Execution timed out 3064 ms 15836 KB Time limit exceeded
22 Halted 0 ms 0 KB -