QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#790842	#8704. 排队	QOJ114514ancestor	100 ✓	477ms	72688kb	C++14	2.2kb	2024-11-28 15:40:44	2024-11-28 15:40:44

Judging History

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

[2024-11-28 15:40:44]
评测

测评结果：100
用时：477ms
内存：72688kb

查看

[2024-11-28 15:40:44]
提交

answer

#include<bits/stdc++.h>
#define int long long
#define N 600005
#define ls tr[u].lss
#define rs tr[u].rss
using namespace std;
int sub,rt,n=1,q,p[N];
set<int> sns[N];
mt19937 rnd(114514);
struct node{int fa,pr,sz,szz,lss,rss;}tr[N];
void nnd(int u){tr[u]=(node){0,rnd(),1,u<=q,0,0};}
int pu(int u){
	return tr[u].sz=tr[ls].sz+tr[rs].sz+1,
	tr[u].szz=tr[ls].szz+tr[rs].szz+(u<=q),
	tr[ls].fa=u,tr[rs].fa=u,tr[u].fa=0,u;}
int mrg(int u,int v){
	if(!min(u,v))return u+v;
	if(tr[u].pr<tr[v].pr)return rs=mrg(rs,v),pu(u);
	return swap(u,v),ls=mrg(v,ls),pu(u);
}
pair<int,int> spt(int u,int sz){
	if(!u)return make_pair(0,0);
	if(sz<=tr[ls].sz){
		auto [a,b]=spt(ls,sz);
		return ls=b,make_pair(a,pu(u));
	}
	auto [a,b]=spt(rs,sz-tr[ls].sz-1);
	return rs=a,make_pair(pu(u),b);
}
void ist(int sz,int u){auto [a,b]=spt(rt,sz);rt=mrg(a,mrg(u,b));}
int rk(int u,int op=1){
	int r=(op|(u<=q))+(op?tr[ls].sz:tr[ls].szz),lst=u;
	while(lst=u,u=tr[u].fa)
		if(lst==rs)r+=(op|(u<=q))+(op?tr[ls].sz:tr[ls].szz);
	return r;
}
void solve(){
	cin>>sub>>q,++q;
	for(int i=1;i<=2*q;i++)nnd(i);
	rt=mrg(1,q+1);
	for(int op,i,x,y,z,qi=1;qi<q;qi++){
		// for(int z=1;z<=n;z++)cerr<<rk(z,0)-1<<' ';
		// cerr<<'\n';
		// for(int z=1;z<=n;z++)cerr<<rk(z)<<' '<<rk(z+q)<<"   ";
		// cerr<<'\n';
		// for(int z=1;z<=n;z++)cerr<<tr[z].fa<<' '<<tr[z+q].fa<<"   ";
		// cerr<<'\n';
		// for(int z=1;z<=n;z++)cerr<<tr[z].sz<<' '<<tr[z+q].sz<<"   ";
		// cerr<<'\n';
		// for(int z=1;z<=n;z++)cerr<<tr[z].lss<<' '<<tr[z].rss<<' '<<tr[z+q].lss<<' '<<tr[z+q].rss<<"   ";
		// cerr<<'\n';
		cin>>op;
		if(op==1)cin>>x,++x,p[++n]=x,sns[x].insert(n),ist(rk(x),mrg(n,n+q));
		else if(op==2){
			cin>>i>>y,++i,++y,x=p[i],p[i]=y;
			sns[x].erase(i),sns[y].insert(i);
			int l=rk(i),r=rk(i+q);
			auto [a,bc]=spt(rt,l-1);
			auto [b,c]=spt(bc,r-l+1);
			rt=mrg(a,c);
			auto it=next(sns[y].find(i));
			if(it==sns[y].end())ist(rk(y),b);
			else ist(rk((*it)+q),b);
		}
		else cin>>z,++z,cout<<rk(z,0)-1<<'\n';
	}
}
signed main(){
	// freopen("a.in","r",stdin);
	// freopen("a.out","w",stdout);
	cin.tie(0)->sync_with_stdio(0);
	int T=1;//cin>>T;
	while(T--)solve();
	return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 4

Accepted

Test #1:

score: 4

Accepted

time: 6ms

memory: 32164kb

input:

output:

result:

ok 4 lines

Test #2:

score: 4

Accepted

time: 8ms

memory: 32640kb

input:

output:

result:

ok 153 lines

Test #3:

score: 4

Accepted

time: 4ms

memory: 32904kb

input:

output:

result:

ok 159 lines

Test #4:

score: 4

Accepted

time: 0ms

memory: 32732kb

input:

output:

result:

ok 145 lines

Subtask #2:

score: 19

Accepted

Test #5:

score: 19

Accepted

time: 162ms

memory: 66304kb

input:

output:

result:

ok 179182 lines

Test #6:

score: 19

Accepted

time: 199ms

memory: 70664kb

input:

output:

result:

ok 98880 lines

Test #7:

score: 19

Accepted

time: 198ms

memory: 68076kb

input:

output:

result:

ok 148504 lines

Test #8:

score: 19

Accepted

time: 163ms

memory: 66700kb

input:

output:

result:

ok 167157 lines

Test #9:

score: 19

Accepted

time: 193ms

memory: 67868kb

input:

output:

result:

ok 145645 lines

Test #10:

score: 19

Accepted

time: 167ms

memory: 67956kb

input:

output:

result:

ok 148730 lines

Test #11:

score: 19

Accepted

time: 121ms

memory: 62852kb

input:

output:

result:

ok 234925 lines

Test #12:

score: 19

Accepted

time: 186ms

memory: 69220kb

input:

output:

result:

ok 126807 lines

Test #13:

score: 19

Accepted

time: 179ms

memory: 69084kb

input:

output:

result:

ok 126007 lines

Test #14:

score: 19

Accepted

time: 211ms

memory: 70428kb

input:

output:

result:

ok 97400 lines

Test #15:

score: 19

Accepted

time: 178ms

memory: 69656kb

input:

output:

result:

ok 117628 lines

Test #16:

score: 19

Accepted

time: 169ms

memory: 64960kb

input:

output:

result:

ok 194540 lines

Test #17:

score: 19

Accepted

time: 247ms

memory: 72156kb

input:

output:

result:

ok 74993 lines

Test #18:

score: 19

Accepted

time: 200ms

memory: 70840kb

input:

output:

result:

ok 98914 lines

Test #19:

score: 19

Accepted

time: 171ms

memory: 66264kb

input:

output:

result:

ok 166650 lines

Subtask #3:

score: 21

Accepted

Test #20:

score: 21

Accepted

time: 134ms

memory: 64036kb

input:

output:

result:

ok 222965 lines

Test #21:

score: 21

Accepted

time: 138ms

memory: 65368kb

input:

output:

result:

ok 197988 lines

Test #22:

score: 21

Accepted

time: 269ms

memory: 72688kb

input:

output:

result:

ok 58684 lines

Test #23:

score: 21

Accepted

time: 192ms

memory: 69236kb

input:

output:

result:

ok 117694 lines

Test #24:

score: 21

Accepted

time: 164ms

memory: 67844kb

input:

output:

result:

ok 147378 lines

Test #25:

score: 21

Accepted

time: 170ms

memory: 67892kb

input:

output:

result:

ok 144784 lines

Test #26:

score: 21

Accepted

time: 191ms

memory: 69492kb

input:

output:

result:

ok 116141 lines

Test #27:

score: 21

Accepted

time: 193ms

memory: 67864kb

input:

output:

result:

ok 147525 lines

Test #28:

score: 21

Accepted

time: 182ms

memory: 67980kb

input:

output:

result:

ok 148070 lines

Test #29:

score: 21

Accepted

time: 191ms

memory: 70172kb

input:

output:

result:

ok 97860 lines

Test #30:

score: 21

Accepted

time: 189ms

memory: 69864kb

input:

output:

result:

ok 96730 lines

Test #31:

score: 21

Accepted

time: 196ms

memory: 70392kb

input:

output:

result:

ok 98247 lines

Test #32:

score: 21

Accepted

time: 158ms

memory: 66824kb

input:

output:

result:

ok 167688 lines

Test #33:

score: 21

Accepted

time: 212ms

memory: 69660kb

input:

output:

result:

ok 117234 lines

Test #34:

score: 21

Accepted

time: 180ms

memory: 68028kb

input:

output:

result:

ok 149568 lines

Subtask #4:

score: 23

Accepted

Test #35:

score: 23

Accepted

time: 435ms

memory: 65324kb

input:

output:

result:

ok 99743 lines

Test #36:

score: 23

Accepted

time: 433ms

memory: 65416kb

input:

output:

result:

ok 99750 lines

Test #37:

score: 23

Accepted

time: 420ms

memory: 65384kb

input:

output:

result:

ok 99683 lines

Subtask #5:

score: 33

Accepted

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Dependency #3:

100%

Accepted

Dependency #4:

100%

Accepted

Test #38:

score: 33

Accepted

time: 366ms

memory: 65320kb

input:

output:

result:

ok 98966 lines

Test #39:

score: 33

Accepted

time: 477ms

memory: 62108kb

input:

output:

result:

ok 48520 lines

Test #40:

score: 33

Accepted

time: 359ms

memory: 61920kb

input:

output:

result:

ok 108743 lines

Test #41:

score: 33

Accepted

time: 371ms

memory: 64704kb

input:

output:

result:

ok 87130 lines

Test #42:

score: 33

Accepted

time: 362ms

memory: 65916kb

input:

output:

result:

ok 74076 lines

Test #43:

score: 33

Accepted

time: 357ms

memory: 64744kb

input:

output:

result:

ok 88582 lines

Test #44:

score: 33

Accepted

time: 215ms

memory: 62660kb

input:

output:

result:

ok 198778 lines

Test #45:

score: 33

Accepted

time: 294ms

memory: 63708kb

input:

output:

result:

ok 145139 lines

Test #46:

score: 33

Accepted

time: 305ms

memory: 61936kb

input:

output:

result:

ok 147109 lines

Test #47:

score: 33

Accepted

time: 300ms

memory: 64652kb

input:

output:

result:

ok 116820 lines

Test #48:

score: 33

Accepted

time: 294ms

memory: 63996kb

input:

output:

result:

ok 150091 lines

Test #49:

score: 33

Accepted

time: 381ms

memory: 67044kb

input:

output:

result:

ok 64514 lines

Test #50:

score: 33

Accepted

time: 271ms

memory: 67796kb

input:

output:

result:

ok 109540 lines

Test #51:

score: 33

Accepted

time: 216ms

memory: 62532kb

input:

output:

result:

ok 197757 lines

Test #52:

score: 33

Accepted

time: 286ms

memory: 66460kb

input:

output:

result:

ok 119220 lines