제출 #964486

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
964486		pcc	The Potion of Great Power (CEOI20_potion)	C++17	70 / 100	3100 ms	151360 KiB

potion

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")
#define pii pair<int,int>
#define fs first
#define sc second

const int mxn = 2e5+10;

int nid[mxn*100],val[mxn*100];
int vcnt = 0;

struct node{
	int head;
	int pl,pr;
};

int add(int now,int v){
	vcnt++;
	nid[vcnt] = now;
	val[vcnt] = v;
	return vcnt;
}

struct SEG{
#define mid ((l+r)>>1)
#define ls seg[now].pl
#define rs seg[now].pr
	node seg[mxn*50];
	int ppp = 0;
	SEG(){}
	int newnode(){
		return ++ppp;
	}
	int modify(int now,int l,int r,int s,int e,int v){
		if(!now)now = newnode();
		if(l>=s&&e>=r){
			seg[now].head = add(seg[now].head,v);
			return now;
		}
		if(mid>=s)ls = modify(ls,l,mid,s,e,v);
		if(mid<e)rs = modify(rs,mid+1,r,s,e,v);
		return now;
	}
	vector<int> re;
	void getval(int now,int l,int r,int p){
		if(!now)return;
		for(int i = seg[now].head;i;i = nid[i])re.push_back(val[i]);
		if(l == r)return;
		if(mid>=p)getval(ls,l,mid,p);
		else getval(rs,mid+1,r,p);
		return;
	}
#undef ls
#undef rs
#undef mid
};

SEG seg;
int arr[mxn],N,D;
int rt[mxn];

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

void curseChanges(int U, int A[], int B[]) {
	map<pii,int> mp;
	for(int i = 0;i<U;i++){
		pii p = {A[i],B[i]};
		if(p.fs>p.sc)swap(p.fs,p.sc);
		if(mp.find(p) != mp.end()){
			rt[p.fs] = seg.modify(rt[p.fs],0,mxn-1,mp[p]+1,i,arr[p.sc]);
			rt[p.sc] = seg.modify(rt[p.sc],0,mxn-1,mp[p]+1,i,arr[p.fs]);
			mp.erase(p);
		}
		else{
			mp[p] = i;
		}
	}
	for(auto &i:mp){
		rt[i.fs.fs] = seg.modify(rt[i.fs.fs],0,mxn-1,i.sc+1,mxn-1,arr[i.fs.sc]);
		rt[i.fs.sc] = seg.modify(rt[i.fs.sc],0,mxn-1,i.sc+1,mxn-1,arr[i.fs.fs]);
	}
	return;
}

int question(int x, int y, int v) {
	seg.re.clear();seg.getval(rt[x],0,mxn-1,v);
	auto ta = seg.re;
	seg.re.clear();seg.getval(rt[y],0,mxn-1,v);
	auto tb = seg.re;
	assert(ta.size()<=500);
	assert(tb.size()<=500);
	sort(ta.begin(),ta.end());
	sort(tb.begin(),tb.end());
	int pt = 0;
	int ans = 1e9;
	for(auto &i:ta){
		while(pt != tb.size()&&tb[pt]<i)pt++;
		if(pt != tb.size())ans = min(ans,abs(i-tb[pt]));
		if(pt-1>=0)ans = min(ans,abs(i-tb[pt-1]));
	}
	return ans;
}

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

potion.cpp: In function 'int question(int, int, int)':
potion.cpp:106:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |   while(pt != tb.size()&&tb[pt]<i)pt++;
      |         ~~~^~~~~~~~~~~~
potion.cpp:107:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |   if(pt != tb.size())ans = min(ans,abs(i-tb[pt]));
      |      ~~~^~~~~~~~~~~~

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