QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#667489#9242. An Easy Geometry Problemred#WA 16ms16380kbC++205.6kb2024-10-22 23:33:292024-10-22 23:33:34

Judging History

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

  • [2024-10-22 23:33:34]
  • 评测
  • 测评结果：WA
  • 用时：16ms
  • 内存：16380kb
查看
  • [2024-10-22 23:33:29]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define mid ((l+r)>>1)
const int mod=998244353;
struct seg_ment
{   
    
    static const int N=2e5+10;
    const int mod=1e9+9;
    const int base=331313131;
    int ans[N<<2];
    int pw[N];
    void init(int n)
    {
        pw[0]=1;
        for(int i=1;i<=n;++i) pw[i]=pw[i-1]*base%mod;
    }
    void update(int pos,int l,int r,int p,int k,int b)
    {
        if(l==r)
        {
            ans[p]=k;
            return;
        }
        if(pos<=mid) update(pos,l,mid,ls(p),k,b);
        else update(pos,mid+1,r,rs(p),k,b);

        if(b==0) //正着
        {
            ans[p]=ans[ls(p)]*pw[r-mid]%mod+ans[rs(p)];
        }
        else //反着
        {
            ans[p]=ans[rs(p)]*pw[mid-l+1]%mod+ans[ls(p)];
        }
        ans[p]=(ans[p]%mod+mod)%mod;
    }
    int query(int tl,int tr,int l,int r,int p,int b)
    {
        if(tl<=l&&r<=tr) return ans[p];
        if(tr<=mid) return query(tl,tr,l,mid,ls(p),b);
        if(tl>mid) return query(tl,tr,mid+1,r,rs(p),b);
        int t1=query(tl,tr,l,mid,ls(p),b);
        int t2=query(tl,tr,mid+1,r,rs(p),b);
        if(b==0) //正着
        {
            return (t1*(min(r,tr)-mid)+t2)%mod;
        }
        else
        {
            return (t2*(mid-max(l,tl)+1)+t1)%mod;
        }
    }
}T[2];

struct seg_ment2
{   
    
    static const int N=2e5+10;
    const int mod=998244353;
    const int base=771717171;
    int ans[N<<2];
    int pw[N];
    void init(int n)
    {
        pw[0]=1;
        for(int i=1;i<=n;++i) pw[i]=pw[i-1]*base%mod;
    }
    void update(int pos,int l,int r,int p,int k,int b)
    {
        if(l==r)
        {
            ans[p]=k;
            return;
        }
        if(pos<=mid) update(pos,l,mid,ls(p),k,b);
        else update(pos,mid+1,r,rs(p),k,b);

        if(b==0) //正着
        {
            ans[p]=ans[ls(p)]*pw[r-mid]%mod+ans[rs(p)];
        }
        else //反着
        {
            ans[p]=ans[rs(p)]*pw[mid-l+1]%mod+ans[ls(p)];
        }
        ans[p]=(ans[p]%mod+mod)%mod;
    }
    int query(int tl,int tr,int l,int r,int p,int b)
    {
        if(tl<=l&&r<=tr) return ans[p];
        if(tr<=mid) return query(tl,tr,l,mid,ls(p),b);
        if(tl>mid) return query(tl,tr,mid+1,r,rs(p),b);
        int t1=query(tl,tr,l,mid,ls(p),b);
        int t2=query(tl,tr,mid+1,r,rs(p),b);
        if(b==0) //正着
        {
            return (t1*(min(r,tr)-mid)+t2)%mod;
        }
        else
        {
            return (t2*(mid-max(l,tl)+1)+t1)%mod;
        }
    }
}P[2];

void solve()
{
    int n,q,k,b;
    cin>>n>>q>>k>>b;
    for (int i=0;i<=1;i++) T[i].init(n),P[i].init(n);
    std::vector<int> a(n+2);
    vector<int> c(n+2);
    vector<int> d(n+2);
    for (int i=1;i<=n;i++) {
        cin>>a[i];
        c[i]=a[i]-a[i-1];
        T[0].update(i,1,n,1,(c[i]+mod)%mod,0);
        d[i]=k-c[i];
        T[1].update(i,1,n,1,(d[i]+mod)%mod,1);

        P[0].update(i,1,n,1,(c[i]+mod)%mod,0);
        // d[i]=k-c[i];
        P[1].update(i,1,n,1,(d[i]+mod)%mod,1);

    }
    //cout<<"why"<<endl;
    while (q--){
        int op;
        cin>>op;
        //cout<<"who "<<op<<endl;
        if (op==1){
            int l,r,v;
            cin>>l>>r>>v;
            c[l]+=v,c[r+1]-=v;
            d[l]=k-c[l],d[r+1]=k-c[r+1];
            T[0].update(l,1,n,1,(c[l]%mod+mod)%mod,0);
            T[1].update(l,1,n,1,(d[l]%mod+mod)%mod,1);

            P[0].update(l,1,n,1,(c[l]%mod+mod)%mod,0);
            P[1].update(l,1,n,1,(d[l]%mod+mod)%mod,1);
            if (r+1<=n){
                T[0].update(r+1,1,n,1,(c[r+1]%mod+mod)%mod,0);
                T[1].update(r+1,1,n,1,(d[r+1]%mod+mod)%mod,1);

                P[0].update(r+1,1,n,1,(c[r+1]%mod+mod)%mod,0);
                P[1].update(r+1,1,n,1,(d[r+1]%mod+mod)%mod,1);
            }
        }
        else{
            int x;
            cin>>x;
            if (x==n||x==1) {
                cout<<0<<"\n";
                continue;
            }
            if (c[x]+c[x+1]==k+b){
                int ans=1;
                int len=min(n-(x+2)+1,x-1-2+1);
                len=max(0ll,len);
                int l=1,r=len;
                while (l<=r){
                    // int mid=(l+r)>>1;
                   // cout<<l<<" "<<r<<" "<<mid<<endl;
                    len=mid;
                    int tmp1=T[0].query(x+2,x+2+len-1,1,n,1,0);
                    int tmp2=T[1].query(x-1-len+1,x-1,1,n,1,1);

                    int tmp3=P[0].query(x+2,x+2+len-1,1,n,1,0);
                    int tmp4=P[1].query(x-1-len+1,x-1,1,n,1,1);


                    tmp1=(tmp1%mod+mod)%mod;
                    tmp2=(tmp2%mod+mod)%mod;

                    tmp3=(tmp3%mod+mod)%mod;
                    tmp4=(tmp4%mod+mod)%mod;
                   // cout<<x+2<<",,,"<<x+2+len-1<<endl;
                   // cout<<tmp1<<" hahah "<<tmp2<<endl;
                    if (tmp1==tmp2&&tmp3==tmp4){
                        ans=mid+1;
                        l=mid+1;
                    }
                    else r=mid-1;
                }
                cout<<ans<<"\n";
            }
            else cout<<0<<"\n";
           // for (int i=1;i<=n;i++) cout<<c[i]<<" ";
           //     cout<<endl;
           // for (int i=1;i<=n;i++) cout<<d[i]<<" ";
           //     cout<<endl;
        }
    }

}


signed main()
{
    ios::sync_with_stdio(false);cin.tie(0);cin.tie(0);
    int t=1;
    //cin>>t;
    for(int i=1;i<=t;i++)
    {
        solve();
    }
    return 0;
}
源文件, 语言: C++20

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 16120kb

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:

1
0
2
0

result:

ok 4 number(s): "1 0 2 0"

Test #2:

score: -100
Wrong Answer
time: 16ms
memory: 16380kb

input:

5000 5000 2 0
-329 -328 -327 -326 -325 -324 -323 -322 -321 -320 -319 -318 -317 -316 -315 -314 -313 -312 -311 -310 -309 -308 -307 -306 -305 -304 -303 -302 -301 -300 -299 -298 -297 -296 -295 -294 -293 -292 -291 -290 -289 -288 -287 -286 -285 -284 -283 -282 -281 -280 -279 -278 -277 -276 -275 -274 -273 -...

output:

2
5
3
3
2
2
2
3
2
2
2
2
2
5
2
2
5
3
3
2
2
2
2
2
2
2
2
1
2
2
3
2
3
2
3
2
2
2
5
2
1
2
5
3
2
2
2
4
2
3
2
2
2
3
3
2
2
2
4
2
4
2
2
5
2
2
2
2
2
2
5
3
2
2
2
2
2
2
2
2
2
3
4
5
5
2
2
2
1
2
2
4
5
2
2
5
2
2
3
2
3
2
2
3
3
3
2
2
4
3
5
2
2
2
2
2
2
3
2
2
2
5
3
2
3
2
2
5
5
2
2
2
2
3
2
0
2
3
2
3
2
3
1
2
2
3
3
2
3
2
...

result:

wrong answer 2nd numbers differ - expected: '304', found: '5'
English 繁體中文 简体中文

伺服器時間: 2024-11-30 01:27:23 | 開源專案