Submission #1063014

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063014		belgianbot	Infinite Race (EGOI24_infiniterace2)	C++17	100 / 100	111 ms	14260 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int N = 2000000;

struct node
{
	node* left, *right;
	bool ahead; 
	bool lazy;
	bool value;
};

int query(node* root, int left, int right, int qLeft, int qRight) 
{
	if (left > qRight || right < qLeft) return -1; 
	if (left >= qLeft && right <= qRight) {
		if (root->lazy){
			root->lazy = false;
			root->ahead = root->value;
		}
		return root->ahead; 
	}
	
	int mid = (left + right) / 2;
	
	if (root->lazy) {
		root->lazy = false;
		root->left->lazy = true;
		root->right->lazy = true;
		root->left->value = root->value;
		root->right->value = root->value;
	}
	int one = query(root->left, left, mid, qLeft, qRight);
	if (one != -1) return one;
	return query(root->right, mid + 1, right, qLeft, qRight); 
}

void update(node* root, int left, int right, int qLeft, int qRight, bool nValue) 
{
	if (left > qRight || right < qLeft) return;
	if (left >= qLeft && right <= qRight) 
	{
		if (left == right) root->ahead = nValue;
		else {
			root->lazy = true;
			root->value = nValue;
		 }
		return;
	}
	
	int mid = (left + right) / 2; 
	
	update(root->left, left, mid, qLeft, qRight, nValue);
	update(root->right, mid + 1, right, qLeft, qRight, nValue);
	
}

void build(node* root, int left, int right, const vector< bool > &v) 
{
	if (left == right) 
	{
		root->ahead = v[left]; 
		return;
	}
	
	int mid = (left + right) / 2; 

	root->left = new node{NULL, NULL, 0, false, false}; 
	root->right = new node{NULL, NULL, 0, false, false}; 
	
	build(root->left, left, mid, v); 
	build(root->right, mid + 1, right, v); 
	
}

void destroy(node* root) 
{
	if (root->left) destroy(root->left); 
	if (root->right) destroy(root->right);
	delete root; 
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	node *root = new node {NULL, NULL, false, false, false};
	int n, Q; cin >> n >> Q;
	int ans = 0;
	vector<bool> v(n, true);
	build(root, 0, n - 1, v);
	for (int i = 0; i < Q; i++) {
		int x; cin >> x;
		if (x < 0) update(root, 0, n - 1, -x, -x, true);
		else {
			if (query(root, 0, n - 1, x, x)) update(root, 0, n - 1, x, x, false);
			else {
				ans++;
				update(root, 0, n - 1, 0, x - 1, true);
				update (root, 0, n-1, x + 1, n - 1, true);
				update(root, 0, n - 1, x, x, false);
			}
		}
	}
	cout << ans << '\n';
	destroy(root);
	return 0;
}
				
				
				

• Subtask 1: 29 / 29
• Subtask 2: 34 / 34
• Subtask 3: 22 / 22
• Subtask 4: 15 / 15