QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#858183#9676. Ancestorswrkwrk0 1894ms179404kbC++2312.3kb2025-01-16 14:47:592025-01-16 14:48:01

Judging History

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

  • [2025-01-16 14:48:01]
  • 评测
  • 测评结果：0
  • 用时：1894ms
  • 内存：179404kb
查看
  • [2025-01-16 14:47:59]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
bool st;
namespace _wrk{;
ostream& operator<<(ostream &w,__int128 p){
	static char buf[45];
	auto *c=buf;
	if(p<0){
		w<<'-';
		p=-p;
	}
	if(p==0){
		w<<'0';
	}else{
		while(p){
			(*c++)=(p%10+'0');
			p/=10;
		}
		c--;
		while(1){
			w<<(*c);
			if(c==buf)break;
			c--;
		}
	}
	return w;
}
istream& operator>>(istream &w,__int128 &p){
	static bool mask;
	mask=0;
	while(isspace(w.peek())){
		w.get();
	}
	if(w.peek()=='-'){
		mask=1;
		w.get();
		if(!isdigit(w.peek())){
			w.putback('-');
			return w;
		}
	}
	p=0;
	while(isdigit(w.peek())){
		char c=w.get();
		p=p*10+(c-'0');
	}
	if(mask)p=-p;
	return w;
}
template<int mod>
struct modint{
	int num;
	const static __uint128_t brt=((__uint128_t)(1)<<(64))/mod;
	modint(){
		num=0;
	}
	modint(int x){
		num=x%mod;
	}
	modint(long long x){
		num=x%mod;
	}
	modint<mod>operator=(int x){
		num=x%mod;
		return (*this);
	}
	modint<mod>operator=(long long x){
		num=x%mod;
		return (*this);
	}
	modint<mod>operator=(modint<mod>x){
		num=x.num;
		return (*this);
	}
	modint<mod> operator+(modint<mod> c)const{
		long long x=num+c.num;
		return x>=mod?x-mod:x;
	}
	modint<mod> operator-(modint<mod> c)const{
		long long x=num-c.num;
		return x<0?x+mod:x;
	}
	modint<mod>operator*(modint<mod>c)const{
		long long x=(long long)num*c.num;
		x=x-mod*(brt*x>>64);
		while(x>=mod)x-=mod;
		return x;
	}
	modint<mod>fpof(long long x)const{
		if(x<0)return inv().fpof(-x);
		if(x==0)return 1;
		auto c=((*this)*(*this)).fpof(x/2);
		if(x&1)return c*(*this);
		else return c;
	}
	struct modint_pow{
		int pf;
		modint_pow(int x){
			pf=x;
		}
		modint_pow(modint<mod> x){
			pf=x.num;
		}
		modint_pow operator+(modint_pow x){
			return pf+x.pf;
		}
	};
	modint_pow operator*(){
		return modint_pow(num);
	}
	modint<mod> operator*(modint_pow x){
		return (*this).fpof(x.pf);
	}
	modint<mod>inv()const{
		return fpof(mod-2);
	}
	modint<mod>operator/(modint<mod>c){
		return (*this)*c.inv();
	}
	operator int(){
		return num;
	}

	modint<mod>operator+=(modint<mod> c){
		return (*this)=(*this)+c;
	}
	modint<mod>operator-=(modint<mod> c){
		return (*this)=(*this)-c;
	}
	modint<mod>operator*=(modint<mod> c){
		return (*this)=(*this)*c;
	}
	modint<mod>operator/=(modint<mod> c){
		return (*this)=(*this)/c;
	}
	modint<mod>operator-(){
		return mod-num;
	}
	friend ostream& operator<<(ostream &w,modint<mod>&&x){
		w<<x.num;
		return w;
	}
	friend istream& operator>>(istream &w,modint<mod>&x){
		w>>x.num;
		x.num%=mod;
		return w;

	}
	bool operator==(modint<mod>x){
		return num==x.num;
	}

};

//#define int long long

template<class type,int N>
struct matrix{
	type a[N+2][N+2];
	int n;
	type* operator[](int pos){
		return a[pos];
	}
	matrix<type,N> operator*(matrix<type,N>b){
		matrix<type,N>ans;
		ans.n=n;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				for(int k=1;k<=n;k++){
					ans[i][j]+=a[i][k]*b[k][j];
				}
			}
		}
		return ans;
	}
};
template<class type>
type fp(type a,int b){
	if(b==0)return type();
	if(b==1)return a;
	type w=fp(a*a,b/2);
	if(b%2)return w*a;
	return w;
}
template<int N>
struct yw_int_array{
	struct three21bit{
		int a:21;
		int b:21;
		int c:21;
	}a[N/3+2];
	struct ref{
		three21bit& s;
		char type;
		operator int(){
			if(type==0)return s.a;
			if(type==1)return s.b;
			return s.c;
		}
		ref& operator=(int x){
			if(type==0)s.a=x;
			else if(type==1)s.b=x;
			else s.c=x;
			return (*this);
		}
	};
	ref operator[](int pos){
		char w=pos%3;
		return {a[pos/3],(char)w};
	}
};
template<class type,int N>
struct backup_array{
	type name[N+5];
	vector<vector<pair<int,int>>>cc;
	void new_array(){
		cc.push_back(vector<pair<int,int>>());
	}
	backup_array(){
		cc.resize(1);
	}
	struct x{
		int id;
		type* name;
		vector<vector<pair<int,int>>> &cc;
		operator type(){
			return name[id];
		}
		type operator=(type w){
			cc.back().push_back({id,name[id]});
			name[id]=w;
			return w;
		}
	};
	x operator[](int pos){
		return {pos,name,cc};
	}
	void backup(){
		reverse(cc.back().begin(),cc.back().end());
		for(auto &x:cc.back()){
			name[x.first]=x.second;
		}
		cc.pop_back();
	}
};
template<class type,int N>
struct Math{
	type jc[N+5],inv[N+5],invjc[N+5];
	Math(){
		jc[0]=jc[1]=inv[1]=invjc[1]=invjc[0]=1;
		for(int i=2;i<=N;i++){
			jc[i]=jc[i-1]*type(i);
		}
		invjc[N]=type(1)/jc[N];
		for(int i=N-1;i>=2;i--){
			invjc[i]=invjc[i+1]*type(i+1);
		}
		for(int i=1;i<=N;i++){
			inv[i]=invjc[i]*jc[i-1];
		}
	}
	type binom(int a,int b){
		return jc[a]*invjc[b]*invjc[a-b];
	}
	type catalan(int n){
		return binom(2*n,n)/type(n+1);
	}
};
template<class type,int num,int maxnum>
struct pows{
	type w[maxnum+5];
	pows(){
		w[0]=type(1);
		for(int i=1;i<=maxnum;i++)w[i]=w[i-1]*type(num);
	}
	type operator[](int pos){
		return w[pos];
	}
};
#ifdef hash
namespace hashing{
	constexpr static int N=5000006;//5e6
	constexpr static int count=1;
	constexpr static int mods[count]={1000000007};
	constexpr static int bases[count]={37};
	constexpr static char start='a';
	int hash_base[count][N+5];
	void init(){
		for(int i=0;i<count;i++){
			hash_base[i][0]=1;
			for(int j=1;j<=N+2;j++){
				hash_base[i][j]=hash_base[i][j-1]*bases[i]%mods[i];
			}
		}
	}
	struct hash{
		int size;
		int has[count];
	};
	bool operator==(const hash&a,const hash&b){
		if(a.size!=b.size)return 0;
		for(int i=0;i<count;i++){
			if(a.has[i]!=b.has[i])return 0;
		}
		return 1;
	}
	hash operator+(const hash&a,const hash&b){
		hash res;
		res.size=a.size+b.size;
		for(int i=0;i<count;i++){
			res.has[i]=(a.has[i]*hash_base[i][b.size]%mods[i]+b.has[i])%mods[i];
		}
		return res;
	}
	hash operator*(const hash&a,int b){
		if(!b)return {};
		if(b==1)return a;
		auto c=(a+a)*(b/2);
		if(b&1)return c+a;
		return c;
	}
	struct hashing_base{
		int p[count][N+5];
		int n;
		void init(const string&c,int l,int r){
			n=r-l+1;
			for(int i=0;i<count;i++){
				int cnt=1;
				for(int j=l;j<=r;j++){
					p[i][cnt]=(p[i][cnt-1]*bases[i]+(c[j]-'a'))%mods[i];
					cnt++;
				}
			}
		}
		void init(const string&c){
			init(c,0,(int)c.size()-1);
		}
		hash substr(int l,int r){
			hash res;
			res.size=r-l+1;
			for(int i=0;i<count;i++){
				res.has[i]=(p[i][r]-p[i][l-1]*hash_base[i][r-l+1]%mods[i]+mods[i])%mods[i];
			}
			return res;
		}
		hash operator[](int pos){
			return substr(pos,pos);
		}
		hash operator[](pair<int,int>pos){
			return substr(pos.first,pos.second);
		}
	};

};
#endif
#ifdef use_seg_tree
template<class type,class laz_type,int len>
struct segment_tree{
	type a[len<<2];
	laz_type laz[len<<2];
	void pushup(int now){
		PUSHUP_VALUE
	}
	void pushdown(int now,int l,int r){
		PUSHDOWN_VALUE
	}
	void build(int now,int l,int r){
		if(l+1==r){
			FIRST_VALUE
			return;
		}
		LAZ_CLEAR
		int mid=(l+r)>>1;
		build(now<<1,l,mid);
		build(now<<1|1,mid,r);
		pushup(now);
	}
	void do1(int now,int l,int r,int L,int R,...){
		if(l+1!=r)pushdown(now,l,r);
		if(R<=l||r<=L)return;
		if(L<=l&&r<=R){
			FULL_BLOCK_VALUE
			return;
		}
		int mid=(l+r)>>1;
		do1(now<<1,l,mid,L,R,...);
		do1(now<<1|1,mid,r,L,R,...);
		pushup(now);
	}
	void do1_one(int now,int l,int r,int p,...){
		if(l+1!=r)pushdown(now,l,r);
		if(l+1==r){
			DO1_VALUE
			return;
		}
		int mid=(l+r)>>1;
		if(p<mid)do1_one(now<<1,l,mid,p,...);
		else do1_one(now<<1|1,mid,r,p,...);
		pushup(now);
	}
	type qu1(int now,int l,int r,int L,int R){
		if(l+1!=r)pushdown(now,l,r);
		if(R<=l||r<=L)return BASE_VALUE
		if(L<=l&&r<=R)return a[now];
		int mid=(l+r)>>1;
		return RETURN_VALVE qu1(now<<1,l,mid,L,R)+qu1(now<<1|1,mid,r,L,R);
	}
	type qu1_one(int now,int l,int r,int p){
		if(l+1!=r)pushdown(now,l,r);
		if(l+1==r)return a[now];
		int mid=(l+r)>>1;
		if(p<mid)return qu1_one(now<<1,l,mid,p);
		else return qu1_one(now<<1|1,mid,r,p);

	}
};
#endif
template<class typea,class typeb>
ostream& operator<<(ostream &w,pair<typea,typeb>z){
	w<<'('<<z.first<<','<<z.second<<')';
	return w;
}
//#define mod 998244353
//#define mint modint<mod>
//pows<mint,2,10000007>tp;note the size
//Math<mint,1000006>math;
vector<int>g[1000006];
int f[1000006]; 
int l[1000006],r[1000006],x[1000006];
int dep[1000006],siz[1000006];
vector<pair<pair<int,int>,pair<int,int>>>zz[1000006];
unordered_map<int,set<int>>z[1000006];
int pre[1000006];
void dfs(int now,int fa){
	dep[now]=dep[fa]+1;
	set<int>change;
	for(auto x:g[now])if(x!=fa){
		dfs(x,now);
		if(siz[x]>siz[now]){
			swap(siz[x],siz[now]);
			swap(z[x],z[now]);
		}
		for(const auto &p:z[x]){
			const auto &se=p.second;
			for(const auto &q:se){
				z[now][p.first].insert(q);
				auto x=z[now][p.first].find(q);
				if(x!=z[now][p.first].begin()){
					pre[*x]=*prev(x);
					change.insert(*x);
				}
				if(next(x)!=z[now][p.first].end()){
					pre[*next(x)]=*x;
					change.insert(*next(x));
				}
			}
		}
		siz[now]+=siz[x]; 
	}
	for(auto p:change){
		int delta=dep[p]-dep[now]; 
		auto x=zz[p].back();
		zz[p].back().second.second=delta-1;
		x.first.first=pre[p]+1;
		x.second.first=delta;
		zz[p].push_back(x);
	}
	zz[now].push_back({{1,now},{0,dep[now]-1}});
	z[now][dep[now]]={now};
	pre[now]=0;
	siz[now]++;
}
struct p{
	int l,r,x,id;
	array<int,4>ge(){
		return {r,l,x,id};
	}
};
struct cmp{
	bool operator()(p a,p b){
		return a.ge()<b.ge();
	}
};
struct bit{
	int a[1000016];
	vector<int>clearbuf;
	bool beclear[1000016];
	int ma;
	void clear(int maxpos){
		for(auto p:clearbuf){
			a[p]=0;
			beclear[p]=0;
		}
		clearbuf.clear();
		ma=maxpos+2;
	}
	int lowbit(int x){
		return x&(-x);
	}
	void ad(int l,int r,int c){
		if(l>r)return;
		if(l){
			ad(0,r,c);
			ad(0,l-1,-c);
			return;
		}
		r++;
		while(r){
			if(!beclear[r]){
				beclear[r]=1;
				clearbuf.push_back(r);
			}
			a[r]+=c;
			r-=lowbit(r);
		}
	}
	void ad(const pair<pair<int,int>,int>&f){
		ad(f.first.first,f.first.second-1,f.second);
	}
	int ge(int p){
		int res=0;
		while(p<=ma){
			res+=a[p];
			p+=lowbit(p);
		} 
		return res;
	}
}bb;
vector<p>ques[1000006]; 
void dd(vector<int>&p){
	sort(p.begin(),p.end());
	p.erase(unique(p.begin(),p.end()),p.end()); 
}
int fpos(const vector<int>&p,int x){
	return lower_bound(p.begin(),p.end(),x)-p.begin();
}
vector<pair<pair<int,int>,int>>dc[1000006];
vector<pair<int,int>>qus[1000006];
int ans[1000006];
void solve(int l,int r){
	if(l+1==r)return;
	int mid=(l+r)>>1;
	vector<int>llsh,xlsh;
	for(int i=l;i<mid;i++){
		for(auto p:zz[i]){
			int x0=p.first.first,x1=p.first.second,y0=p.second.first,y1=p.second.second;
			llsh.push_back(x0);
			llsh.push_back(x1+1);
			xlsh.push_back(y0);
			xlsh.push_back(y1+1);
		}
	}
	for(int i=mid;i<r;i++){
		for(auto p:ques[i]){
			int x=p.l,y=p.x;
			llsh.push_back(x);
			xlsh.push_back(y);
		}
	}
	dd(llsh);
	dd(xlsh);
	for(int i=0;i<llsh.size();i++){
		dc[i].clear();
		qus[i].clear();
	}
	for(int i=l;i<mid;i++){
		for(auto p:zz[i]){
			int x0=p.first.first,x1=p.first.second,y0=p.second.first,y1=p.second.second;
			x0=fpos(llsh,x0);
			x1=fpos(llsh,x1+1);
			y0=fpos(xlsh,y0);
			y1=fpos(xlsh,y1+1);
			dc[x0].push_back({{y0,y1},1});
			dc[x1].push_back({{y0,y1},-1});
			
		}
	}
	for(int i=mid;i<r;i++){
		for(auto p:ques[i]){
			int x=p.l,y=p.x,id=p.id;;
			x=fpos(llsh,x);
			y=fpos(xlsh,y);
			qus[x].push_back({y,id});
		}
	}
	bb.clear(xlsh.size()+1);
	for(int i=0;i<llsh.size();i++){
		for(auto p:dc[i]){
			bb.ad(p);
		}
		for(auto f:qus[i]){
			ans[f.second]+=bb.ge(f.first);
		}
	}
	solve(l,mid);
	solve(mid,r);
}	
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int n,q;
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>f[i];
		g[f[i]].push_back(i);
	}
	for(int i=1;i<=q;i++){
		cin>>l[i]>>r[i]>>x[i];
		ques[r[i]+1].push_back({l[i],r[i],x[i],i}); 
	}
	int root=g[0].back();
	dfs(root,0);
	for(int i=1;i<=n;i++){
		for(auto p:zz[i]){
			cout<<p<<',';
		}
		cout<<'\n';
	}
	solve(1,n+2);
	for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
	return 0;
}
}
bool en;
signed main(){
	#ifdef LOCAL_WRK
	cerr<<"[Static Memory : "<<fixed<<((&st)-(&en))/1048576.0<<"MB]"<<endl;
	#endif
	#ifdef hash
	_wrk::hashing::init();
	#endif
	   return _wrk::main();
}
源文件, 语言: C++23

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 15ms
memory: 75508kb

input:

7 5
3 1 0 5 3 5 1
1 3 1
5 7 2
1 5 1
4 7 1
4 7 2

output:

((1,1),(0,1)),
((1,2),(0,2)),
((1,3),(0,0)),
((1,4),(0,1)),((3,4),(2,2)),
((1,5),(0,0)),((2,5),(1,1)),
((1,6),(0,0)),((5,6),(1,1)),((5,6),(2,2)),
((1,7),(0,0)),((3,7),(1,1)),((7,7),(2,2)),
3
3
5
4
3

result:

wrong output format Expected integer, but "((1,1),(0,1))," found

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Wrong Answer

Test #30:

score: 0
Wrong Answer
time: 604ms
memory: 114904kb

input:

50000 200000
42574 43129 47328 17982 40521 6668 12729 32377 201 11940 8599 11734 18349 41045 26854 22540 9897 33419 7463 1243 47272 27135 49050 49111 22435 42539 39924 20272 5843 9308 45963 3283 31185 13692 38952 20583 15885 24802 4773 953 49907 28689 36942 23550 19449 8970 33340 31665 5407 46023 18...

output:

((1,1),(0,30678)),
((1,2),(0,49327)),
((1,3),(0,18601)),
((1,4),(0,31568)),
((1,5),(0,883)),
((1,6),(0,38402)),
((1,7),(0,4847)),
((1,8),(0,41646)),
((1,9),(0,12304)),
((1,10),(0,43189)),
((1,11),(0,13853)),
((1,12),(0,15104)),
((1,13),(0,18342)),
((1,14),(0,11436)),
((1,15),(0,43600)),
((1,16),(0,3...

result:

wrong output format Expected integer, but "((1,1),(0,30678))," found

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Wrong Answer

Test #67:

score: 0
Wrong Answer
time: 1894ms
memory: 179404kb

input:

100000 1000000
6457 23693 90928 23592 90440 75018 16865 3342 83718 16731 95103 31510 38719 27886 29093 41955 6596 46409 51839 10527 91993 61074 14405 34833 53674 42363 11490 43757 46191 6058 59164 96938 57858 40178 97523 84164 21582 72243 11267 47368 97058 6637 95208 60092 53943 16441 28363 64965 52...

output:

((1,1),(0,85160)),
((1,2),(0,65622)),
((1,3),(0,1069)),
((1,4),(0,53724)),
((1,5),(0,82989)),
((1,6),(0,20290)),
((1,7),(0,26311)),
((1,8),(0,78686)),
((1,9),(0,92697)),
((1,10),(0,21699)),
((1,11),(0,45166)),
((1,12),(0,85780)),
((1,13),(0,60362)),
((1,14),(0,24864)),
((1,15),(0,56933)),
((1,16),(0...

result:

wrong output format Expected integer, but "((1,1),(0,85160))," found

Subtask #6:

score: 0
Skipped

Dependency #1:

0%
English 繁體中文 简体中文

伺服器時間: 2025-01-21 06:31:27 | 開源專案