제출 #808817

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
808817		andrey27_sm	The Potion of Great Power (CEOI20_potion)	C++17	38 / 100	3053 ms	156144 KiB

potion

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 17 / 17
• Subtask 3: 0 / 14
• Subtask 4: 0 / 18
• Subtask 5: 21 / 21
• Subtask 6: 0 / 30