QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#611845 | #9242. An Easy Geometry Problem | crush_codemaker | WA | 3ms | 24732kb | C++14 | 4.8kb | 2024-10-04 23:13:18 | 2024-10-04 23:13:18 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define N 200007
#pragma GCC optimize(2)
using namespace std;
int n,q,k,b;
int A[N];
struct Node
{
int h1,h2,sz;
bool operator == (const Node &other) const
{
return h1==other.h1&&h2==other.h2&&sz==other.sz;
}
};
struct segment_tree
{
Node tr[N<<2];
int tg[N<<2];
int cf1[N],cf2[N];
int ta1[N],ta2[N];
int b1=100007,b2=99997;
int p1=998244353,p2=1e9+7;
Node mge(Node x,Node y)
{
return {(y.h1+(x.h1*cf1[y.sz])%p1)%p1,(y.h2+(x.h2*cf2[y.sz])%p2)%p2,x.sz+y.sz};
}
void pu(int i)
{
tr[i]=mge(tr[i<<1],tr[i<<1|1]);
}
void pd(int i,int l,int r)
{
if(!tg[i])
{
return ;
}
int mid=(l+r)>>1;
tg[i<<1]+=tg[i];
tg[i<<1|1]+=tg[i];
tr[i<<1].h1=(tr[i<<1].h1+((tg[i]%p1)*ta1[mid-l+1])%p1)%p1;
tr[i<<1].h2=(tr[i<<1].h2+((tg[i]%p2)*ta2[mid-l+1])%p2)%p2;
tr[i<<1|1].h1=(tr[i<<1|1].h1+((tg[i]%p1)*ta1[r-mid])%p1)%p1;
tr[i<<1|1].h2=(tr[i<<1|1].h2+((tg[i]%p2)*ta2[r-mid])%p2)%p2;
tg[i]=0;
}
void bd(int i,int l,int r)
{
if(l==r)
{
tr[i].h1=tr[i].h2=0;
tr[i].sz=r-l+1;
tg[i]=0;
}
else
{
int mid=(l+r)>>1;
bd(i<<1,l,mid);
bd(i<<1|1,mid+1,r);
tr[i].h1=tr[i].h2=0;
tr[i].sz=r-l+1;
tg[i]=0;
}
}
void up(int x,int L,int R,int i,int l,int r)
{
if(L<=l&&r<=R)
{
tg[i]+=x;
tr[i].h1=(tr[i].h1+((x%p1)*ta1[r-l+1])%p1)%p1;
tr[i].h2=(tr[i].h2+((x%p2)*ta2[r-l+1])%p2)%p2;
}
else
{
int mid=(l+r)>>1;
pd(i,l,r);
if(L<=mid)
{
up(x,L,R,i<<1,l,mid);
}
if(R>mid)
{
up(x,L,R,i<<1|1,mid+1,r);
}
pu(i);
}
}
Node qq(int L,int R,int i,int l,int r)
{
if(L<=l&&r<=R)
{
return tr[i];
}
else
{
int mid=(l+r)>>1;
pd(i,l,r);
if(L<=mid&&R>mid)
{
return mge(qq(L,R,i<<1,l,mid),qq(L,R,i<<1|1,mid+1,r));
}
else if(L<=mid&&!(R>mid))
{
return qq(L,R,i<<1,l,mid);
}
else if(!(L<=mid)&&R>mid)
{
return qq(L,R,i<<1|1,mid+1,r);
}
else
{
return {0,0,0};
}
}
}
void init()
{
bd(1,1,n);
cf1[0]=1;
for(int i=1;i<=n;i++)
{
cf1[i]=(cf1[i-1]*b1)%p1;
}
cf2[0]=1;
for(int i=1;i<=n;i++)
{
cf2[i]=(cf2[i-1]*b2)%p2;
}
ta1[0]=0;
for(int i=1;i<=n;i++)
{
ta1[i]=(1+(ta1[i-1]*b1)%p1)%p1;
}
ta2[0]=0;
for(int i=1;i<=n;i++)
{
ta2[i]=(1+(ta2[i-1]*b2)%p2)%p2;
}
}
void upd(int x,int L,int R)
{
up(x,L,R,1,1,n);
}
Node qur(int L,int R)
{
return qq(L,R,1,1,n);
}
};
struct DS
{
segment_tree st1,st2;
void init()
{
st1.init();
st2.init();
for(int i=1;i<=n;i++)
{
st1.upd(2*A[i]-k*i-2*b+(int)(1e10),i,i);
st2.upd(2*A[i]-k*i+(int)(1e10),n+1-i,n+1-i);
}
}
void upd(int x,int L,int R)
{
st1.upd(2*x,L,R);
st2.upd(2*x,n+1-R,n+1-L);
}
int check(int x,int y)
{
if(y==0)
{
return 1;
}
return st1.qur(x+1,x+y)==st2.qur(n+1-(x-1),n+1-(x-y));
}
int qur(int x)
{
int l=0,r=min(n-x,x-1);
while(l<r)
{
int mid=(l+r+1)>>1;
if(check(x,mid))
{
l=mid;
}
else
{
r=mid-1;
}
}
int ans=l;
return ans;
}
};
DS ds;
void solve()
{
//scanf("%lld%lld%lld%lld",&n,&q,&k,&b);
n=5000;q=5000;k=2;b=0;
for(int i=1;i<=n;i++)
{
//scanf("%lld",&A[i]);
A[i]=i+792;
}
ds.init();
while(q--)
{
int op;
scanf("%lld",&op);
if(op==1)
{
int l,r,x;
scanf("%lld%lld%lld",&l,&r,&x);
ds.upd(x,l,r);
}
else if(op==2)
{
int x;
scanf("%lld",&x);
int ans=ds.qur(x);
printf("%lld\n",ans);
}
}
}
signed main()
{
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 24732kb
input:
6 6 6 2 1 5 9 10 15 18 2 2 1 3 3 -3 2 2 1 3 4 3 2 3 2 4
output:
0 1 0 0 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 ...
result:
wrong answer 1st numbers differ - expected: '1', found: '0'