QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#600597	#5000. Balanced Seesaw Array	yld	WA	367ms	18120kb	C++20	4.2kb	2024-09-29 17:35:23	2024-09-29 17:35:24

Judging History

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

[2024-09-29 17:35:24]
评测

测评结果：WA
用时：367ms
内存：18120kb

查看

[2024-09-29 17:35:23]
提交

answer

#include<bits/stdc++.h>
#define int long long 
#define endl '\n'
#define ls rt<<1
#define rs rt<<1|1
using namespace std;
const int MAXN=1e5+5;
struct SegmentTree{
    int l,r,sum,mul,lazy1,lazy2;
}tree[MAXN<<2];
int a[MAXN];
void update(int rt)
{
    tree[rt].sum=tree[ls].sum+tree[rs].sum;
    tree[rt].mul=tree[ls].mul+tree[rs].mul;
}
void build(int l,int r,int rt)
{
    tree[rt].lazy1=tree[rt].lazy2=1e18;
    tree[rt].l=l,tree[rt].r=r;
    if(l==r) {tree[rt].sum=a[l],tree[rt].mul=a[l]*l;return;}
    int mid=l+r>>1;
    build(l,mid,ls);
    build(mid+1,r,rs);
    update(rt);
}
void pushdown(int rt)
{
    if(tree[rt].lazy1!=1e18)
    {
        tree[ls].lazy1=tree[rs].lazy1=tree[rt].lazy1;
        tree[ls].sum=(tree[ls].r-tree[ls].l+1)*tree[rt].lazy1;
        tree[rs].sum=(tree[rs].r-tree[rs].l+1)*tree[rt].lazy1;
        tree[ls].mul=(tree[ls].l+tree[ls].r)*(tree[ls].r-tree[ls].l+1)/2*tree[rt].lazy1;
        tree[rs].mul=(tree[rs].l+tree[rs].r)*(tree[rs].r-tree[rs].l+1)/2*tree[rt].lazy1;
        tree[ls].lazy2=tree[rs].lazy2=1e18;
        tree[rt].lazy1=1e18;
    }
    if(tree[rt].lazy2!=1e18)
    {
        tree[ls].lazy2+=tree[rt].lazy2;
		tree[rs].lazy2+=tree[rt].lazy2;
        tree[ls].sum+=(tree[ls].r-tree[ls].l+1)*tree[rt].lazy2;
        tree[rs].sum+=(tree[rs].r-tree[rs].l+1)*tree[rt].lazy2;
        tree[ls].mul+=(tree[ls].l+tree[ls].r)*(tree[ls].r-tree[ls].l+1)/2*tree[rt].lazy2;
        tree[rs].mul+=(tree[rs].l+tree[rs].r)*(tree[rs].r-tree[rs].l+1)/2*tree[rt].lazy2;
        tree[rt].lazy2=1e18;
    }
}
void modify(int l,int r,int rt,int c)
{
    if(l<=tree[rt].l && tree[rt].r<=r)
    {
        tree[rt].lazy1=c;
        tree[rt].lazy2=1e18;
        tree[rt].sum=(tree[rt].r-tree[rt].l+1)*c;
        tree[rt].mul=(tree[rt].r-tree[rt].l+1)*(tree[rt].r+tree[rt].l)/2*c;
        return;
    }
    int mid=tree[rt].l+tree[rt].r>>1;
    pushdown(rt);
    if(l<=mid) modify(l,r,ls,c);
    if(r>mid) modify(l,r,rs,c);
    update(rt);
}
void add(int l,int r,int rt,int c)
{
    if(l<=tree[rt].l && tree[rt].r<=r)
    {
        tree[rt].lazy2+=c;
        tree[rt].sum+=(tree[rt].r-tree[rt].l+1)*c;
        tree[rt].mul+=(tree[rt].r-tree[rt].l+1)*(tree[rt].r+tree[rt].l)/2*c;
        return;
    }
    int mid=tree[rt].l+tree[rt].r>>1;
    pushdown(rt);
    if(l<=mid) add(l,r,ls,c);
    if(r>mid) add(l,r,rs,c);
    update(rt);
}
pair<int,int> query(int l,int r,int rt)
{
    if(l<=tree[rt].l && tree[rt].r<=r) return {tree[rt].mul,tree[rt].sum};
    int mid=tree[rt].l+tree[rt].r>>1;
    pushdown(rt);
    pair<int,int> ans={0,0};
    if(l<=mid)
    {
        pair<int,int> temp=query(l,r,ls);
        ans.first+=temp.first,ans.second+=temp.second;
    }
    if(r>mid)
    {
        pair<int,int> temp=query(l,r,rs);
        ans.first+=temp.first,ans.second+=temp.second;
    }
    return ans;
}
int n,q;
void solve()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,n,1);
    // cerr<<tree[5].l<<' '<<tree[5].r<<' '<<tree[5].sum<<endl;
    while(q--)
    {
        int op,l,r;
        cin>>op>>l>>r;
        // cerr<<tree[4].sum<<' '<<tree[5].sum<<' '<<tree[3].sum<<endl;
        if(op==1)
        {
            int x;cin>>x;
            // cerr<<l<<' '<<r<<' '<<x<<endl;
            add(l,r,1,x);
            // cerr<<tree[4].sum<<' '<<tree[5].sum<<' '<<tree[3].sum<<endl;
        }
        else if(op==2)
        {
            int x;cin>>x;
            modify(l,r,1,x);
        }
        else
        {
            // cerr<<l<<' '<<r<<endl;
            pair<int,int>temp;
            int m=r-l+1;
            temp=query(l,r,1);
            temp.first-=(l-1)*temp.second;
            // cerr<<temp.first<<' '<<temp.second<<endl;
            if(temp.second==0)
            {
                if(temp.first==0) cout<<"Yes\n";
                else cout<<"No\n";
            }
            else if(temp.first%temp.second==0 && temp.first/temp.second<=m && temp.first/temp.second>=1) cout<<"Yes\n";
            else cout<<"No\n";
            // cerr<<"==============\n";
        }
    }
}
signed main()
{
    cin.tie(0);
    int t=1;
    while(t--) solve();
    return 0;
}

源文件, 语言: C++20

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 3648kb

input:

output:

Yes
No
Yes
Yes

result:

ok 4 lines

Test #2:

score: -100

Wrong Answer

time: 367ms

memory: 18120kb

input:

100000 451163
-18 609 -793 393 375 313 -55 -892 -446 928 -207 -390 729 -383 27 318 -400 31 -661 202 -978 212 238 -368 351 -613 -23 400 809 1000 -431 -174 -103 886 73 -150 25 820 -689 972 777 794 -36 -231 -966 632 -418 -288 -476 725 -713 -379 896 -19 -883 338 -797 937 -557 -809 -241 -539 704 44 576 -...

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
Yes
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No...

result:

wrong answer 2nd lines differ - expected: 'Yes', found: 'No'