oj.uz

Submission #808817

# Submission time Handle Problem Language Result Execution time Memory
808817 2023-08-05T11:24:25 Z andrey27_sm The Potion of Great Power (CEOI20_potion) C++17
38 / 100
 3000 ms 156144 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr ll mod = 1e9+7;
pair<int,int> h[100000];
int tr[100000];
int n,d;
struct edges{
	struct Node{
		int val;
		int ls;
		int rs;
	};
	vector<int> roots;
	vector<Node> Nodes;
	vector<int> updates;
	int update(int v,int l,int r,int target){
		if(r < target) return v;
		if(target < l) return v;
		if(l == r){
			int old_val = 0;
			if(v != -1) old_val = Nodes[v].val;
			v = Nodes.size();
			Nodes.push_back({old_val^1,-1,-1});
			return v;
		}
		int m = (l+r)/2;
		int tmp_l;
		int tmp_r;
		if(v != -1) tmp_l = update(Nodes[v].ls,l,m,target);
		else tmp_l = update(-1,l,m,target);
		if(v != -1) tmp_r = update(Nodes[v].rs,m+1,r,target);
		else tmp_r = update(-1,m+1,r,target);
		int v2 = Nodes.size();
		Nodes.push_back({0,tmp_l,tmp_r});
		if(Nodes[v2].ls != -1) Nodes[v2].val+=Nodes[Nodes[v2].ls].val;
		if(Nodes[v2].rs != -1) Nodes[v2].val+=Nodes[Nodes[v2].rs].val;
		if(Nodes[v2].val == 0){
			Nodes.pop_back();
			return -1;
		}
		return v2;
	}
	void add(int x,int id){
		updates.push_back(id);
		if(roots.empty()) roots.push_back(update(-1,0,n-1,x));
		else roots.push_back(update(roots.back(),0,n-1,x));
	}
	void get_g(int v,int l,int r,vector<int> &ans){
		if(v == -1) return;
		if(Nodes[v].val == 0) return;
		if(l == r){
			ans.push_back(l);
			return;
		}
		int m = (l+r)/2;
		get_g(Nodes[v].ls,l,m,ans);
		get_g(Nodes[v].rs,m+1,r,ans);
	}
	void get(int id, vector<int> &ans){
		auto it = upper_bound(updates.begin(), updates.end(),id);
		if(it == updates.begin()) return;
		int id_max = it-updates.begin()-1;
		get_g(roots[id_max],0,n-1,ans);
	}

} E[100001];
void init(int N, int D, int H[]) {
	n = N;
	for (int i = 0; i < n; ++i)
	{
		h[i] = {H[i],i};
	}
	sort(h,h+n);
	for (int i = 0; i < n; ++i)
	{
		tr[h[i].second] = i;
	}
	d = D;
}

void curseChanges(int U, int A[], int B[]) {
	for (int i = 0; i < U; ++i)
	{
		E[tr[A[i]]].add(tr[B[i]],i);
		E[tr[B[i]]].add(tr[A[i]],i);
	}
}

int question(int x, int y, int v) {
	//cout << x << " " << y << " " << v << "\n";
	if(v == 0) return 1e9;
 	x = tr[x];
 	y = tr[y];
 	vector<int> frx;
 	E[x].get(v-1,frx);
 	vector<int> fry;
 	E[y].get(v-1,fry);
 	int ans_max = 1e9;
 	vector<int> hx;
 	vector<int> hy;
 	for(auto e:frx) hx.push_back(h[e].first);
 	for(auto e:fry) hy.push_back(h[e].first);
    int p = 0;
    for (int i = 0; i < hx.size(); ++i)
    {
    	while(p < hy.size() and hy[p] <= hx[i]) p++;
    	if(p) ans_max = min(ans_max,abs(hx[i]-hy[p-1]));
    	if(p < hy.size()) ans_max = min(ans_max,abs(hx[i]-hy[p]));
    }
    return ans_max;
}

Compilation message

potion.cpp: In function 'int question(int, int, int)':
potion.cpp:105:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     for (int i = 0; i < hx.size(); ++i)
      |                     ~~^~~~~~~~~~~
potion.cpp:107:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |      while(p < hy.size() and hy[p] <= hx[i]) p++;
      |            ~~^~~~~~~~~~~
potion.cpp:109:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |      if(p < hy.size()) ans_max = min(ans_max,abs(hx[i]-hy[p]));
      |         ~~^~~~~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7248 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7760 KB Output is correct
2 Correct 5 ms 7760 KB Output is correct
3 Correct 6 ms 7760 KB Output is correct
4 Correct 22 ms 9732 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 696 ms 156144 KB Output is correct
2 Correct 657 ms 156144 KB Output is correct
3 Correct 352 ms 75324 KB Output is correct
4 Correct 2071 ms 89756 KB Output is correct
5 Correct 1071 ms 130764 KB Output is correct
6 Execution timed out 3053 ms 103376 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 632 ms 156024 KB Output is correct
2 Execution timed out 3035 ms 83944 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 12696 KB Output is correct
2 Correct 120 ms 10876 KB Output is correct
3 Correct 191 ms 10684 KB Output is correct
4 Correct 911 ms 11372 KB Output is correct
5 Correct 752 ms 12056 KB Output is correct
6 Correct 150 ms 11848 KB Output is correct
7 Correct 666 ms 11128 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7248 KB Output is correct
2 Correct 5 ms 7760 KB Output is correct
3 Correct 5 ms 7760 KB Output is correct
4 Correct 6 ms 7760 KB Output is correct
5 Correct 22 ms 9732 KB Output is correct
6 Correct 696 ms 156144 KB Output is correct
7 Correct 657 ms 156144 KB Output is correct
8 Correct 352 ms 75324 KB Output is correct
9 Correct 2071 ms 89756 KB Output is correct
10 Correct 1071 ms 130764 KB Output is correct
11 Execution timed out 3053 ms 103376 KB Time limit exceeded
12 Halted 0 ms 0 KB -