QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#224678 | #5441. Quartz Collection | ZSH_ZSH# | RE | 1ms | 8056kb | C++14 | 3.7kb | 2023-10-23 09:10:21 | 2023-10-23 09:10:22 |
Judging History
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...