QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#224678#5441. Quartz CollectionZSH_ZSH#RE 1ms8056kbC++143.7kb2023-10-23 09:10:212023-10-23 09:10:22

Judging History

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

  • [2023-10-23 09:10:22]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:8056kb
  • [2023-10-23 09:10:21]
  • 提交

answer

#include<bits/stdc++.h>
#define rep(i,a,b) for (register int i=(a);i<=(b);i++)
#define drep(i,a,b) for (register int i=(a);i>=(b);i--)
typedef long long ll;
using namespace std;

const int N=300010;

int n,a[N],b[N],m;

struct info
{
	int ls,rs,rnd,tag,val,X,size;
	ll sum;
}t[N];
inline void push_up(int x)
{
	t[x].sum=t[x].val;
	if (t[x].ls) t[x].sum+=t[t[x].ls].sum;
	if (t[x].rs) t[x].sum+=t[t[x].rs].sum;
	t[x].size=1;
	if (t[x].ls) t[x].size+=t[t[x].ls].size;
	if (t[x].rs) t[x].size+=t[t[x].rs].size;
}
void setcov(int node)
{
	t[node].tag^=1;
	t[node].val=-t[node].val;
	t[node].sum=-t[node].sum;
}
inline void push_down(int x)
{
	if (t[x].tag)
	{
		if (t[x].ls) setcov(t[x].ls);
		if (t[x].rs) setcov(t[x].rs);
		t[x].tag=0;
	}
}
array<int,2> split(int x,int X)
{
	if (!x) return {0,0};
	push_down(x);
	if (t[x].X<=X)
	{
		auto rs=split(t[x].rs,X);
		t[x].rs=rs[0];
		push_up(x);
		return {x,rs[1]};
	}
	else
	{
		auto ls=split(t[x].ls,X);
		t[x].ls=ls[1];
		push_up(x);
		return {ls[0],x};
	}
}
array<int,2> splitsz(int x,int X)
{
	if (!x) return {0,0};
	push_down(x);
	if (t[t[x].ls].size+1<=X)
	{
		auto rs=split(t[x].rs,X-1-t[t[x].ls].size);
		t[x].rs=rs[0];
		push_up(x);
		return {x,rs[1]};
	}
	else
	{
		auto ls=split(t[x].ls,X);
		t[x].ls=ls[1];
		push_up(x);
		return {ls[0],x};
	}
}
int merge(int x,int y)
{
	if (!x||!y) return x+y;
	push_down(x);
	push_down(y);
	if (t[x].rnd<t[y].rnd)
	{
		t[x].rs=merge(t[x].rs,y);
		push_up(x);
		return x;
	}
	else
	{
		t[y].ls=merge(x,t[y].ls);
		push_up(y);
		return y;
	}
}
mt19937 rng(time(0));
int rt[5],cnt;

void ins(int x)
{
//	printf("ins %d\n",x);
	if (x<=0)
	{
		array<int,2> s[4];
		rep(i,0,3) s[i]=split(rt[i],x);
		t[++cnt].rnd=rng();
		t[cnt].X=x;
		t[cnt].val=x;
		t[cnt].sum=x;
		t[cnt].size=1;
		int id=0;
		rep(i,0,3) id+=t[s[i][0]].size;
		id++; id%=4;
//		printf("x %d id %d\n",x,id);
		s[id][0]=merge(s[id][0],cnt);
		rep(i,0,3) rt[i]=merge(s[i][0],s[(i+3)%4][1]);
	}
	else
	{
//		printf("here??\n");
		auto s=split(rt[4],x);
		t[++cnt].rnd=rng();
		t[cnt].X=x;
		t[cnt].val=t[cnt].sum=((t[s[0]].size%2==1)?x:-x);
		t[cnt].size=1;
		if (s[1]) setcov(s[1]);
//		printf("s0 %d cnt %d s1 %d\n",s[0],cnt,s[1]);
		rt[4]=merge(merge(s[0],cnt),s[1]);
	}
}
void del(int x)
{
//	printf("del %d\n",x);
	if (x<=0)
	{
		array<int,2> s[4];
		rep(i,0,3) s[i]=split(rt[i],x);
		int id=0;
		rep(i,0,3) id+=t[s[i][0]].size;
		id%=4;
		{
			assert(t[s[id][0]].size);
			auto ss=splitsz(s[id][0],t[s[id][0]].size-1);
			s[id][0]=ss[0];
		}
		rep(i,0,3) rt[i]=merge(s[i][0],s[(i+1)%4][1]);
	}
	else
	{
		auto s=split(rt[4],x);
		assert(t[s[0]].size);
		auto ss=splitsz(s[0],t[s[0]].size-1);
		if (s[1]) setcov(s[1]);
		rt[4]=merge(ss[0],s[1]);
	}
}

ll xns;
void solve()
{
	ll ans=xns;
	ans+=t[rt[0]].sum+t[rt[1]].sum; 
	ans-=t[rt[2]].sum+t[rt[3]].sum; 
//	printf("nowans %lld\n",ans);
//	rep(i,0,4) printf("rt i %d : %d sum %lld\n",i,rt[i],t[rt[i]].sum);
	int sz=0;
	rep(i,0,3) sz+=t[rt[i]].size;
//	printf("sz %d\n",sz);
	sz%=2;
	if (sz==0)
	{
		ans-=t[rt[4]].sum;
	}
	else ans+=t[rt[4]].sum;
	printf("%lld\n",ans/2);
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
	
	cin>>n>>m;
	rep(i,1,n) cin>>a[i]>>b[i],a[i]*=2,b[i]*=2;
	
	rep(i,1,n)
	{
		xns+=(a[i]+b[i])/2;
		ins((a[i]-b[i])/2);
	}
//	printf("xns %lld\n",xns);
	solve();
	rep(i,1,m)
	{
		int t,A,B; cin>>t>>A>>B;
		A*=2; B*=2;
		xns-=((a[t]+b[t])/2);
		del((a[t]-b[t])/2);
		a[t]=A,b[t]=B;
		xns+=((a[t]+b[t])/2);
		ins((a[t]-b[t])/2);
		solve();
	}
//	printf("%lld\n",ans+t[rt].sum);
	
	return 0;
}
/*
4 5
2 4
5 7
1 7
2 1
4 5 2
1 6 2
4 4 3
2 1 3
3 6 6

*/

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 8056kb

input:

4 5
2 4
5 7
1 7
2 1
4 5 2
1 6 2
4 4 3
2 1 3
3 6 6

output:

13
14
15
14
10
13

result:

ok 6 numbers

Test #2:

score: 0
Accepted
time: 1ms
memory: 6008kb

input:

1 1
1 1
1 1 1

output:

1
1

result:

ok 2 number(s): "1 1"

Test #3:

score: -100
Runtime Error

input:

100 100
6 7
100 8
5 61
5 75
59 65
51 47
83 37
34 54
87 46
4 26
21 87
12 97
86 68
60 11
62 76
14 83
29 31
91 62
57 80
47 75
85 97
62 77
91 86
14 25
48 77
83 65
39 61
78 77
45 46
90 74
100 91
86 98
55 5
84 42
91 69
100 4
74 98
60 37
75 44
41 12
15 34
36 1
99 16
7 87
36 26
79 42
41 84
17 98
72 16
38 55...

output:


result: