Submission #1160249

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160249		dibamboo23	The Potion of Great Power (CEOI20_potion)	C++20	100 / 100	1897 ms	71456 KiB

potion

#include <bits/stdc++.h>

using namespace std;

#define sz size()
#define S second
#define F first

const int N=(int)2e5+3;

int h[N];
int n;

void init(int N, int D, int H[]) {
	for(int i=0;i<N;i++)h[i]=H[i];
}

vector<pair<int,int>>t[N*4];

void upd(int l,int r,pair<int,int>x,int v=1,int tl=1,int tr=n){
	if(tl>=l&&tr<=r){
		t[v].push_back(x);
		t[v].push_back({x.S,x.F});
		return;
	}
	if(tl>r||l>tr)return;
	int md=(tl+tr)>>1;
	upd(l,r,x,v+v,tl,md);
	upd(l,r,x,v+v+1,md+1,tr);
}

void sort_tree(int v=1,int tl=1,int tr=n){
	sort(t[v].begin(),t[v].end());
	if(tl==tr)return;
	int md=(tl+tr)>>1;
	sort_tree(v+v,tl,md);
	sort_tree(v+v+1,md+1,tr);
}

set<pair<pair<int,int>,int>>st;

void curseChanges(int U, int A[], int B[]) {
	n=U;
	for(int i=0;i<n;i++){
		if(A[i]>B[i])swap(A[i],B[i]);
		auto it=st.lower_bound({{A[i],B[i]},-1});
		if(it==st.end()||it->F.F!=A[i]||it->F.S!=B[i]){
			st.insert({{A[i],B[i]},i});
		}
		else{
			int l=it->S+1,r=i+1;
			st.erase(it);
			upd(l,r-1,{A[i],B[i]});
		}
	}
	for(auto [to,pos]:st)upd(pos+1,n,to);
	sort_tree();
}

int needA,needB;
vector<int>nowA,nowB;

void get(int pos,int v=1,int tl=1,int tr=n){
	int j=lower_bound(t[v].begin(),t[v].end(),make_pair(needA,-1))-t[v].begin();
	for(;j<(int)t[v].sz;j++){
		if(t[v][j].F!=needA)break;
		nowA.push_back(h[t[v][j].S]);
	}
	j=lower_bound(t[v].begin(),t[v].end(),make_pair(needB,-1))-t[v].begin();
	for(;j<(int)t[v].sz;j++){
		if(t[v][j].F!=needB)break;
		nowB.push_back(h[t[v][j].S]);
	}
	if(tl==tr)return;
	int md=(tl+tr)>>1;
	if(pos<=md)get(pos,v+v,tl,md);
	else get(pos,v+v+1,md+1,tr);
}

int question(int x, int y, int v) {
	needA=x;
	needB=y;
	nowA.clear();
	nowB.clear();
	get(v);
	if(nowA.empty()||nowB.empty())return (int)1e9;
	sort(nowA.begin(),nowA.end());
	sort(nowB.begin(),nowB.end());
	int mn=(int)1e9;
	int j=0;
	for(auto to:nowA){
		while(j<(int)nowB.sz-1&&nowB[j]<to)j++;
		mn=min(mn,abs(nowB[j]-to));
		if(j>0)mn=min(mn,abs(nowB[j-1]-to));
	}
	return mn;
}

// int main() {
  // int N, D, U, Q;
  // std::ios::sync_with_stdio(false); std::cin.tie(NULL);
  // std::cin >> N >> D >> U >> Q;
// 
  // int *F = new int[N];
  // for (int i=0; i<N; i++)
    // std::cin >> F[i];
  // init(N, D, F);
// 
  // int *A = new int[U], *B = new int[U];
  // for (int i=0; i<U; i++) {
    // std::cin >> A[i] >> B[i];
  // }
  // curseChanges(U, A, B);
// 
  // bool correct = true;
  // for (int i=0; i<Q; i++) {
    // int X,Y,V,CorrectAnswer;
    // std::cin >> X >> Y >> V >> CorrectAnswer;
    // int YourAnswer = question(X,Y,V);
    // if (YourAnswer != CorrectAnswer) {
      // std::cout << "WA! Question: " << i
		// << " (X=" << X << ", Y=" << Y << ", V=" << V << ") "
		// <<  "Your answer: " << YourAnswer
                // << " Correct Answer: " << CorrectAnswer << std::endl;
      // correct = false;
    // } else {
      // std::cerr << YourAnswer << " - OK" << std::endl;
    // }
  // }
// 
  // if (correct) {
    // std::cout << "Correct." << std::endl;
  // } else std::cout << "Incorrect." << std::endl;
  // return 0;
// }

• Subtask 1: 0 / 0
• Subtask 2: 17 / 17
• Subtask 3: 14 / 14
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 30 / 30