QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#852387	#8704. 排队	wanggiaoxing	100 ✓	498ms	68508kb	C++14	2.6kb	2025-01-11 11:36:45	2025-01-11 11:36:47

Judging History

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

[2025-01-11 11:36:47]
评测

测评结果：100
用时：498ms
内存：68508kb

查看

[2025-01-11 11:36:45]
提交

answer

#include<bits/stdc++.h>
#define int long long
//#define int __int128
#define ll long long
#define pa pair<int,int>
//#define int unsigned long long
#define sg signed
#define fi first
#define se second
#define ls s[x][0]
#define rs s[x][1]
#define ld long double
#define bs basic_string
const int inf=1e18;
using namespace std;
inline int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {
        if(ch=='-')w=-1;
        ch=getchar();
    }
    while(ch<='9'&&ch>='0')
        s=s*10+ch-'0',ch=getchar();
    return s*w;
}
int sub,n,siz[600005],s[600005][2],fa[600005],val[6000005],num[6000005];
int sum[6000005];
void up(int x){
	fa[x]=0;
	siz[x]=siz[ls]+siz[rs]+1;
	sum[x]=sum[ls]+sum[rs]+num[x];
	if(ls)fa[ls]=x;
	if(rs)fa[rs]=x;
}
void spilt(int x,int k,int &a,int &b){
	if(!x){
		a=b=0;
		return;
	}
	if(siz[ls]+1<=k){
		a=x;
		spilt(rs,k-siz[ls]-1,rs,b);
	}else{
		b=x;
		spilt(ls,k,a,ls);
	}
	up(x);
}
int merge(int x,int y){
	if(!x||!y)return x+y;
	if(val[x]<val[y]){
		rs=merge(rs,y);
		up(x);
		return x;
	}else{
		s[y][0]=merge(x,s[y][0]);
		up(y);
		return y;
	}
}
int get(int x){
	if(!x)return 0;
	int now=siz[ls]+1;
	while(fa[x]){
		int k=fa[x];
		if(s[k][1]==x)now+=siz[s[k][0]]+1;
		x=fa[x];
	}
	return now;
}
int get1(int x){
	if(!x)return 0;
	int now=sum[ls]+num[x];
	while(fa[x]){
		int k=fa[x];
		if(s[k][1]==x)now+=sum[s[k][0]]+num[k];
		x=fa[x];
	}
	return now;
}
int in[300005],out[300005],rt;
int Fa[300005];
set<int>S[300005];
set<int>::iterator it;
mt19937 rd(time(0));
void ins(int x,int pos,int val1){
	int a,b;
	spilt(rt,pos,a,b);
	num[x]=sum[x]=val1;
	val[x]=rd();
	siz[x]=1;
	rt=merge(merge(a,x),b);
}
void solve(){
	sub=read(),n=read();
	int tot=0,cnt=0;
	for(int i=1;i<=n;i++){
		int op=read();
		if(op==1){
			int x1=read();
			int x=get(in[x1]);tot++;
//			cout<<"Q "<<i<<" "<<x<<endl;
			ins(in[tot]=++cnt,x,1);
			ins(out[tot]=++cnt,x+1,0);
//			cout<<get(in[tot])<<" "<<get(out[tot])<<endl;
			S[x1].insert(tot);
			Fa[tot]=x1;
		}else if(op==2){
			int id=read(),x=read();
			if(Fa[id]==x)continue;
			S[Fa[id]].erase(id);
			it=S[x].lower_bound(id);
			int pos;
			if(it!=S[x].end())pos=get(out[*it]);
			else pos=get(in[x]);
			int L=get(in[id]),R=get(out[id]);
			if(pos>R)pos-=(R-L+1);
			int a,b,c,d;
			spilt(rt,L-1,a,b);
			spilt(b,R-L+1,c,d);
			rt=merge(a,d);
			spilt(rt,pos,a,b);
			rt=merge(merge(a,c),b);
			Fa[id]=x;
			S[x].insert(id);
		}else printf("%lld\n",get1(in[read()]));
	}
}
signed main(){
	int t=1;while(t--)solve();
    return 0;
}
/*
0 4
1 0
1 1
1 2
3 2
*/

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: 3ms

memory: 29520kb

input:

output:

result:

ok 4 lines

Test #2:

score: 4

Accepted

time: 0ms

memory: 28940kb

input:

output:

result:

ok 153 lines

Test #3:

score: 4

Accepted

time: 0ms

memory: 28540kb

input:

output:

result:

ok 159 lines

Test #4:

score: 4

Accepted

time: 5ms

memory: 29776kb

input:

output:

result:

ok 145 lines

Subtask #2:

score: 19

Accepted

Test #5:

score: 19

Accepted

time: 182ms

memory: 49568kb

input:

output:

result:

ok 179182 lines

Test #6:

score: 19

Accepted

time: 202ms

memory: 60244kb

input:

output:

result:

ok 98880 lines

Test #7:

score: 19

Accepted

time: 213ms

memory: 54220kb

input:

output:

result:

ok 148504 lines

Test #8:

score: 19

Accepted

time: 148ms

memory: 52348kb

input:

output:

result:

ok 167157 lines

Test #9:

score: 19

Accepted

time: 222ms

memory: 56480kb

input:

output:

result:

ok 145645 lines

Test #10:

score: 19

Accepted

time: 170ms

memory: 54868kb

input:

output:

result:

ok 148730 lines

Test #11:

score: 19

Accepted

time: 115ms

memory: 37804kb

input:

output:

result:

ok 234925 lines

Test #12:

score: 19

Accepted

time: 229ms

memory: 55860kb

input:

output:

result:

ok 126807 lines

Test #13:

score: 19

Accepted

time: 194ms

memory: 58840kb

input:

output:

result:

ok 126007 lines

Test #14:

score: 19

Accepted

time: 209ms

memory: 62992kb

input:

output:

result:

ok 97400 lines

Test #15:

score: 19

Accepted

time: 237ms

memory: 58264kb

input:

output:

result:

ok 117628 lines

Test #16:

score: 19

Accepted

time: 154ms

memory: 47816kb

input:

output:

result:

ok 194540 lines

Test #17:

score: 19

Accepted

time: 315ms

memory: 67224kb

input:

output:

result:

ok 74993 lines

Test #18:

score: 19

Accepted

time: 222ms

memory: 64048kb

input:

output:

result:

ok 98914 lines

Test #19:

score: 19

Accepted

time: 198ms

memory: 51388kb

input:

output:

result:

ok 166650 lines

Subtask #3:

score: 21

Accepted

Test #20:

score: 21

Accepted

time: 148ms

memory: 44720kb

input:

output:

result:

ok 222965 lines

Test #21:

score: 21

Accepted

time: 150ms

memory: 47956kb

input:

output:

result:

ok 197988 lines

Test #22:

score: 21

Accepted

time: 296ms

memory: 68508kb

input:

output:

result:

ok 58684 lines

Test #23:

score: 21

Accepted

time: 243ms

memory: 56924kb

input:

output:

result:

ok 117694 lines

Test #24:

score: 21

Accepted

time: 179ms

memory: 53652kb

input:

output:

result:

ok 147378 lines

Test #25:

score: 21

Accepted

time: 184ms

memory: 54464kb

input:

output:

result:

ok 144784 lines

Test #26:

score: 21

Accepted

time: 192ms

memory: 56116kb

input:

output:

result:

ok 116141 lines

Test #27:

score: 21

Accepted

time: 224ms

memory: 56320kb

input:

output:

result:

ok 147525 lines

Test #28:

score: 21

Accepted

time: 178ms

memory: 53560kb

input:

output:

result:

ok 148070 lines

Test #29:

score: 21

Accepted

time: 196ms

memory: 63544kb

input:

output:

result:

ok 97860 lines

Test #30:

score: 21

Accepted

time: 213ms

memory: 64988kb

input:

output:

result:

ok 96730 lines

Test #31:

score: 21

Accepted

time: 268ms

memory: 60188kb

input:

output:

result:

ok 98247 lines

Test #32:

score: 21

Accepted

time: 154ms

memory: 52504kb

input:

output:

result:

ok 167688 lines

Test #33:

score: 21

Accepted

time: 251ms

memory: 56712kb

input:

output:

result:

ok 117234 lines

Test #34:

score: 21

Accepted

time: 207ms

memory: 56648kb

input:

output:

result:

ok 149568 lines

Subtask #4:

score: 23

Accepted

Test #35:

score: 23

Accepted

time: 483ms

memory: 48128kb

input:

output:

result:

ok 99743 lines

Test #36:

score: 23

Accepted

time: 498ms

memory: 45808kb

input:

output:

result:

ok 99750 lines

Test #37:

score: 23

Accepted

time: 482ms

memory: 43784kb

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: 417ms

memory: 47940kb

input:

output:

result:

ok 98966 lines

Test #39:

score: 33

Accepted

time: 467ms

memory: 36792kb

input:

output:

result:

ok 48520 lines

Test #40:

score: 33

Accepted

time: 337ms

memory: 35996kb

input:

output:

result:

ok 108743 lines

Test #41:

score: 33

Accepted

time: 389ms

memory: 46316kb

input:

output:

result:

ok 87130 lines

Test #42:

score: 33

Accepted

time: 407ms

memory: 48952kb

input:

output:

result:

ok 74076 lines

Test #43:

score: 33

Accepted

time: 405ms

memory: 42728kb

input:

output:

result:

ok 88582 lines

Test #44:

score: 33

Accepted

time: 207ms

memory: 36552kb

input:

output:

result:

ok 198778 lines

Test #45:

score: 33

Accepted

time: 288ms

memory: 43460kb

input:

output:

result:

ok 145139 lines

Test #46:

score: 33

Accepted

time: 292ms

memory: 38260kb

input:

output:

result:

ok 147109 lines

Test #47:

score: 33

Accepted

time: 334ms

memory: 42616kb

input:

output:

result:

ok 116820 lines

Test #48:

score: 33

Accepted

time: 289ms

memory: 39412kb

input:

output:

result:

ok 150091 lines

Test #49:

score: 33

Accepted

time: 419ms

memory: 52952kb

input:

output:

result:

ok 64514 lines

Test #50:

score: 33

Accepted

time: 280ms

memory: 56340kb

input:

output:

result:

ok 109540 lines

Test #51:

score: 33

Accepted

time: 211ms

memory: 34660kb

input:

output:

result:

ok 197757 lines

Test #52:

score: 33

Accepted

time: 294ms

memory: 50236kb

input:

output:

result:

ok 119220 lines