QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#42834#2305. 历史qiaozhCompile Error//C++4.2kb2022-08-04 10:51:182022-08-04 10:51:19

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-08-04 10:51:19]
  • 评测
查看
  • [2022-08-04 10:51:18]
  • 提交

answer

#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
typedef long long ll;
inline int read()
{
    char ch=getchar();int s=0,w=1;
    while(ch<48||ch>57){if(ch=='-')w=-1;ch=getchar();}
    while(ch>=48&&ch<=57){s=(s<<1)+(s<<3)+ch-48;ch=getchar();}
    return s*w;
}
inline void write(ll x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+48);
}
ll n,m;
vector<ll> G[400010];
struct info {
	ll top,siz,fa,asiz,rak,dep,dfn,son,h,inp,ans;
} f[400010];
ll dfn_ind=0,Ans=0;
class CMP { public:bool operator()(ll ot1,ll ot2) {
	return ot1>ot2;
}};
set<ll,CMP> tre[400010];
void dfs1(ll node,ll last) {
	f[node].siz=1;f[node].fa=last;f[node].son=0;f[node].dep=f[last].dep+1;
	f[node].asiz=f[node].inp;
	for(int i=0;i<G[node].size();i++) {
		if(G[node][i]==last) continue;
		dfs1(G[node][i],node);
		f[node].siz+=f[G[node][i]].siz;f[node].asiz+=f[G[node][i]].asiz;
		if(f[G[node][i]].siz>f[f[node].son].siz) f[node].son=G[node][i];
	}
}
void dfs2(ll node,ll last,ll ctop) {
	f[node].dfn=++dfn_ind;f[node].top=ctop;f[f[node].dfn].rak=node;
	ll mx=f[node].inp,lind=0;
	if(f[node].son!=0) {
		dfs2(f[node].son,node,ctop);
		if(f[f[node].son].asiz>mx) mx=f[f[node].son].asiz,lind=f[node].son;
	}
	for(int i=0;i<G[node].size();i++) {
		if(G[node][i]==last||G[node][i]==f[node].son) continue;
		dfs2(G[node][i],node,G[node][i]);tre[G[node][i]].insert(0);
		if(f[G[node][i]].asiz>mx) mx=f[G[node][i]].asiz,lind=G[node][i];
	}
	if(f[node].asiz*2<=f[f[node].fa].asiz&&node!=1) tre[f[node].top].insert(f[node].dfn);
	if(mx*2>f[node].asiz) {
		Ans+=(f[node].ans=2*(f[node].asiz-mx));
		if(mx==f[node].inp) f[node].h=node;
		else f[node].h=lind;
	} else Ans+=(f[node].ans=f[node].asiz-1);
}
struct BIT {
	ll va[400010],col[400010],ti[400010],la[400010];
	void init() {
		for(int i=1;i<=n;i++) va[i]=0;
		for(int i=1;i<=n;i++) col[i]=f[f[i].rak].top;
		ti[1]=1;
		for(int i=2;i<=n;i++) {
			if(col[i]==col[i-1]) ti[i]=ti[i-1];
			else ti[i]=i;
		}
		la[n]=n;
		for(int i=n-1;i>=1;i--) {
			if(col[i]==col[i+1]) la[i]=la[i+1];
			else la[i]=i;
		}
		col[0]=-1;
	}
	inline void cun(ll ind,ll k) { 
		ll tu=ti[ind];
		for(int i=ind-tu+1;i>=1;i-=(i&-i)) va[i+tu-1]+=k;
	}
	inline ll cha(ll ind) {
		ll ret=0,tu=ti[ind],lu=la[ind];
		for(int i=ind-tu+1;i+tu-1<=lu;i+=(i&-i)) ret+=va[i+tu-1];
		return ret;
	}
} btre;
inline void prealter(ll node,ll k) {
	f[node].inp+=k;
	while(node!=0) {
		btre.cun(f[node].dfn,k);
//		if(node) btre.cun(f[f[node].top].dfn-1,-k);
		node=f[f[node].top].fa;
	}
}
inline void update(ll node,ll ch,ll k,ll jinp) {
	Ans-=f[node].ans;
	ll A=btre.cha(f[node].dfn),B=btre.cha(f[f[node].h].dfn),C=btre.cha(f[ch].dfn);
	if(f[node].h!=0&&f[node].h!=node) {
		if(B*2<=A) tre[f[f[node].h].top].insert(f[f[node].h].dfn),f[node].h=0;
	} else if(f[node].h==node) {
		if(f[node].inp*2<=A) f[node].h=0;
	}
	if(C*2>A) {
		if(f[node].h!=ch) tre[f[ch].top].erase(f[ch].dfn),f[node].h=ch,B=btre.cha(f[f[node].h].dfn);
	} else if(f[node].inp*2>A) f[node].h=node;
	if(f[node].h!=0&&f[node].h!=node) {
		Ans+=(f[node].ans=2*(A-B));
	} else if(f[node].h==node) {
		Ans+=(f[node].ans=2*(A-f[node].inp));
	} else Ans+=(f[node].ans=A-1);
}
void alter(ll node,ll k) {
	ll fn=f[node].top,cur,fath;
	if(f[node].son) update(node,f[node].son,k,k);
	while(node!=0) {
		if(f[node].fa&&f[f[node].fa].h!=node) update(f[node].fa,node,k,0);
		cur=f[node].dfn;
		cur=(*tre[fn].upper_bound(cur));
		while(cur>=f[fn].dfn) {
			node=f[cur].rak;fath=f[node].fa;
			update(fath,node,k,0);
			cur=(*tre[fn].upper_bound(cur));
		}
		node=f[fn].fa;fn=f[node].top;
	}
}
int main() {
//	freopen("ex_history2.in","r",stdin);
//	freopen("pu.out","w",stdout);
	n=read();m=read();
	for(int i=1;i<=n;i++) f[i].inp=read();
	ll u,v;
	for(int i=1;i<=n-1;i++) {
		u=read();v=read();
		G[u].push_back(v);G[v].push_back(u);
	}
	dfs1(1,0);dfs2(1,0,1);btre.init();tre[1].insert(0);
	for(int i=1;i<=n;i++) {
		btre.cun(f[i].dfn,f[i].asiz);
		if(i!=f[i].top) btre.cun(f[i].dfn-1,-f[i].asiz);
	}
	write(Ans);putchar('\n');
	for(int i=1;i<=m;i++) {
		u=read();v=read();prealter(u,v);
		alter(u,v);write(Ans);putchar('\n');
	}
	return 0;
}
源文件, 语言: C++

詳細信息 

In file included from /usr/include/c++/11/map:60,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:81,
                 from answer.code:1:
/usr/include/c++/11/bits/stl_tree.h: In instantiation of ‘static const _Key& std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_S_key(std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Const_Link_type) [with _Key = long long int; _Val = long long int; _KeyOfValue = std::_Identity<long long int>; _Compare = CMP; _Alloc = std::allocator<long long int>; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Const_Link_type = const std::_Rb_tree_node<long long int>*]’:
/usr/include/c++/11/bits/stl_tree.h:2069:47:   required from ‘std::pair<std::_Rb_tree_node_base*, std::_Rb_tree_node_base*> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_get_insert_unique_pos(const key_type&) [with _Key = long long int; _Val = long long int; _KeyOfValue = std::_Identity<long long int>; _Compare = CMP; _Alloc = std::allocator<long long int>; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::key_type = long long int]’
/usr/include/c++/11/bits/stl_tree.h:2122:4:   required from ‘std::pair<std::_Rb_tree_iterator<_Val>, bool> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_insert_unique(_Arg&&) [with _Arg = long long int; _Key = long long int; _Val = long long int; _KeyOfValue = std::_Identity<long long int>; _Compare = CMP; _Alloc = std::allocator<long long int>]’
/usr/include/c++/11/bits/stl_set.h:521:25:   required from ‘std::pair<typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator, bool> std::set<_Key, _Compare, _Alloc>::insert(std::set<_Key, _Compare, _Alloc>::value_type&&) [with _Key = long long int; _Compare = CMP; _Alloc = std::allocator<long long int>; typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator = std::_Rb_tree<long long int, long long int, std::_Identity<long long int>, CMP, std::allocator<long long int> >::const_iterator; typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other = std::allocator<long long int>; typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key> = __gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::rebind<long long int>; typename _Alloc::value_type = long long int; std::set<_Key, _Compare, _Alloc>::value_type = long long int]’
answer.code:47:58:   required from here
/usr/include/c++/11/bits/stl_tree.h:770:15: error: static assertion failed: comparison object must be invocable as const
  770 |               is_invocable_v<const _Compare&, const _Key&, const _Key&>,
      |               ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/11/bits/stl_tree.h:770:15: note: ‘std::is_invocable_v<const CMP&, const long long int&, const long long int&>’ evaluates to false
English 繁體中文 简体中文

伺服器時間: 2024-11-29 19:38:15 | 開源專案