oj.uz

Submission #302407

# Submission time Handle Problem Language Result Execution time Memory
302407 2020-09-18T16:24:54 Z mieszko11b The Potion of Great Power (CEOI20_potion) C++14
52 / 100
 2437 ms 236880 KB 
#include <bits/stdc++.h>

using namespace std;

using ii = pair<int, int>;

#define X first
#define Y second

mt19937 rng;

int rand(int a, int b) {
	return uniform_int_distribution<int>(a, b)(rng);
}

struct node {
	int val, p;
	node *l, *r;
	
	node(int v) {
		l = r = nullptr;
		val = v;
		p = rand(INT_MIN, INT_MAX - 1);
	}
	
	node(node *n) {
		val = n->val;
		p = n->p;
		l = n->l;
		r = n->r;
	}
	
	node* attach(node *l, node *r) {
		this->l = l;
		this->r = r;
		return this;
	}
};

int pr(node *n) {
	if(n == nullptr)
		return INT_MAX;
	return n->p;
}

node* clear(node *n) {
	n->l = n->r = nullptr;
	return n;
}

struct treap {
	vector<node*> root;
	vector<int> day;
	
	treap() {
		day.push_back(0);
		root.push_back(nullptr);
	}
	
	void print(node *n) {
		if(n == nullptr)
			return ;
			
		//~ cout << "[ ";
		//~ print(n->l);
		//~ cout << " ] (" << n->val << ") [ ";
		//~ print(n->r);
		//~ cout << " ]";
	}
	
	void print() {
		print(root.back());
		cout << endl;
	}
	
	void new_root(int d) {
		day.push_back(d);
		if(root.empty()) 
			root.push_back(nullptr);
		else
			root.push_back(root.back());	
	}
	
	node* merge(node *a, node *b) {
		if(a == nullptr)
			return b;
		if(b == nullptr)
			return a;
			
		if(a->p > b->p)
			swap(a, b);
			
		a = new node(a);
		if(b->val < a->val)
			return a->attach(merge(a->l, b), a->r);
		return a->attach(a->l, merge(a->r, b));
	}
	
	pair<node*, node*> split(node *n, int x) {
		if(n == nullptr)
			return {nullptr, nullptr};
		
		n = new node(n);
		if(n->val < x) {
			auto p = split(n->r, x);
			return {n->attach(n->l, p.X), p.Y};
		}
		
		auto p = split(n->l, x);
		return {p.X, n->attach(p.Y, n->r)};
	}
	
	void insert(int x, int d) {
		new_root(d);
		auto p = split(root.back(), x);
		root.back() = merge(merge(p.X, new node(x)), p.Y);
		//~ print();
	}
	
	node* erase(node *n, node *x) {
		if(n->val == x->val)
			return merge(n->l, n->r);
		
		if(x->val < n->val)
			return (new node(n))->attach(erase(n->l, x), n->r);
		else
			return (new node(n))->attach(n->l, erase(n->r, x));
	}
	
	void erase(int x, int d) {
		new_root(d);
		root.back() = erase(root.back(), new node(x));
		//~ print();
	}

	
	vector<int> hlp;
	
	void dfs(node *n) {
		if(n == nullptr)
			return ;
			
		dfs(n->l);
		hlp.push_back(n->val);
		dfs(n->r);
	}
	
	vector<int> get_all(int t) {
		int r = prev(upper_bound(day.begin(), day.end(), t)) - day.begin();
		
		hlp.clear();
		dfs(root[r]);
		return hlp;
	}
};

treap T[100007];
int n, d, u, q;
int h[100007];
set<ii> S;

int closest(vector<int> A, vector<int> B) {
	int res = 1e9;
	int j = 0;
	for(int i = 0 ; i < A.size() ; i++) {
		while(j < B.size() && B[j] < A[i])
			j++;
		if(j < B.size())
			res = min(res, abs(A[i] - B[j]));
		if(j - 1 >= 0)
			res = min(res, abs(A[i] - B[j - 1]));
	}
	return res;
}

void init(int N, int D, int *H) {
	int c = chrono::steady_clock().now().time_since_epoch().count();
	//~ int c = -507409753;
	//~ cout << c << endl;
	rng = mt19937(c);
	n = N;
	d = D;
	for(int i = 0 ; i < n ; i++)
		h[i] = H[i];
}	
		
void curseChanges(int U, int *A, int *B) {	
	for(int i = 0 ; i < U ; i++) {
		int a, b;
		a = A[i];
		b = B[i];
		if(a > b) swap(a, b);
		
		if(S.count({a, b})) {
			//~ cout << "erase " << a << " " << b << endl;
			T[a].erase(h[b], i + 1);
			//~ T[a].print();
			T[b].erase(h[a], i + 1);
			//~ T[b].print();
			S.erase({a, b});
		} else {
			//~ cout << "insert " << a << " " << b << endl;
			T[a].insert(h[b], i + 1);
			//~ T[a].print();
			T[b].insert(h[a], i + 1);
			//~ T[b].print();
			S.insert({a, b});
		}
		//~ cout << endl;
	}
}
	
int question(int X, int Y, int V) {
	return closest(T[X].get_all(V), T[Y].get_all(V));

}

Compilation message

potion.cpp: In function 'int closest(std::vector<int>, std::vector<int>)':
potion.cpp:165:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |  for(int i = 0 ; i < A.size() ; i++) {
      |                  ~~^~~~~~~~~~
potion.cpp:166:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |   while(j < B.size() && B[j] < A[i])
      |         ~~^~~~~~~~~~
potion.cpp:168:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |   if(j < B.size())
      |      ~~^~~~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 13696 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 13952 KB Output is correct
2 Correct 17 ms 13952 KB Output is correct
3 Correct 17 ms 13952 KB Output is correct
4 Correct 33 ms 14584 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 683 ms 80504 KB Output is correct
2 Correct 677 ms 80596 KB Output is correct
3 Correct 367 ms 101496 KB Output is correct
4 Correct 2107 ms 236880 KB Output is correct
5 Correct 1107 ms 173832 KB Output is correct
6 Correct 2437 ms 149368 KB Output is correct
7 Correct 910 ms 99068 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 559 ms 77432 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 16376 KB Output is correct
2 Correct 99 ms 17912 KB Output is correct
3 Correct 108 ms 17280 KB Output is correct
4 Correct 441 ms 20320 KB Output is correct
5 Correct 396 ms 18680 KB Output is correct
6 Correct 121 ms 19832 KB Output is correct
7 Correct 356 ms 19192 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 13696 KB Output is correct
2 Correct 17 ms 13952 KB Output is correct
3 Correct 17 ms 13952 KB Output is correct
4 Correct 17 ms 13952 KB Output is correct
5 Correct 33 ms 14584 KB Output is correct
6 Correct 683 ms 80504 KB Output is correct
7 Correct 677 ms 80596 KB Output is correct
8 Correct 367 ms 101496 KB Output is correct
9 Correct 2107 ms 236880 KB Output is correct
10 Correct 1107 ms 173832 KB Output is correct
11 Correct 2437 ms 149368 KB Output is correct
12 Correct 910 ms 99068 KB Output is correct
13 Incorrect 559 ms 77432 KB Incorrect
14 Halted 0 ms 0 KB -