QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#829140	#9774. Same Sum	ktngii_ver35	WA	993ms	20920kb	C++14	2.3kb	2024-12-24 04:01:26	2024-12-24 04:01:28

Judging History

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

[2025-01-11 11:59:18]
hack成功，自动添加数据
(/hack/1443)

[2024-12-24 04:01:28]
评测

测评结果：WA
用时：993ms
内存：20920kb

查看

[2024-12-24 04:01:26]
提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MX=2e5+10;
const ll hash_value=1e6+5, mod=1e9+7;

int n,q;
ll inv;

ll binpow(ll a, ll n) {
    ll res=1;
    while (n) {
        if (n%2==1) res=(res*a)%mod;
        a=(a*a)%mod;
        n/=2;
    }
    return res;
}

ll sum[4*MX][3],lz[4*MX];

void pushlz(int l, int r, int idx) {
    if (!lz[idx]) return;
    sum[idx][0]+=lz[idx]*(r-l+1);
    if (sum[idx][1]) sum[idx][1]=(sum[idx][1]*binpow(hash_value,lz[idx]))%mod;
    else sum[idx][1]=binpow(hash_value,lz[idx]);
    if (sum[idx][2]) sum[idx][2]=(sum[idx][2]*binpow(inv,lz[idx]))%mod;
    else sum[idx][2]=binpow(inv,lz[idx]);
    if (l!=r) {
        lz[2*idx]+=lz[idx];
        lz[2*idx+1]+=lz[idx];
    }
    lz[idx]=0;
}

void update(int l, int r, int idx, int x, int y, int val) {
    pushlz(l,r,idx);
    if (x>r || y<l) return;
    if (x<=l && r<=y) {
        lz[idx]+=val;
        pushlz(l,r,idx);
    } else {
        int mid=(l+r)/2;
        update(l,mid,2*idx,x,y,val);
        update(mid+1,r,2*idx+1,x,y,val);
        sum[idx][0]=sum[2*idx][0]+sum[2*idx+1][0];
        sum[idx][1]=(sum[2*idx][1]+sum[2*idx+1][1])%mod;
        sum[idx][2]=(sum[2*idx][2]+sum[2*idx+1][2])%mod;
    }
}

vector<ll> query(int l, int r, int idx, int x, int y) {
    pushlz(l,r,idx);
    if (x>r || y<l) return {0,0,0};
    if (x<=l && r<=y) return {sum[idx][0],sum[idx][1],sum[idx][2]};
    int mid=(l+r)/2;
    vector<ll> r1=query(l,mid,2*idx,x,y),r2=query(mid+1,r,2*idx+1,x,y);
    return {r1[0]+r2[0],(r1[1]+r2[1])%mod,(r1[2]+r2[2])%mod};
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    inv=binpow(hash_value,mod-2);
    cin>>n>>q;
    for (int i=1; i<=n; ++i) {
        int x; cin>>x;
        update(1,n,1,i,i,x);
    }
    while (q--) {
        int mode; cin>>mode;
        if (mode==1) {
            int l,r,x; cin>>l>>r>>x;
            update(1,n,1,l,r,x);
        } else {
            int l,r; cin>>l>>r;
            vector<ll> v=query(1,n,1,l,r);
            if ((v[0]*2)%(r-l+1)) cout<<"NO\n";
            else {
                ll s=v[0]*2/(r-l+1);
                if (v[1]==(binpow(hash_value,s)*v[2])%mod) cout<<"YES\n";
                else cout<<"NO\n";
            }
        }
    }
}

源文件, 语言: C++14

詳細信息

Test #1:

score: 100

Accepted

time: 1ms

memory: 3648kb

input:

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

output:

YES
NO
YES

result:

ok 3 token(s): yes count is 2, no count is 1

Test #2:

score: -100

Wrong Answer

time: 993ms

memory: 20920kb

input:

200000 200000
0 0 0 1 1 0 2 1 1 2 0 1 0 0 0 2 1 0 1 2 2 1 2 1 2 0 0 2 1 2 1 0 0 2 0 2 1 1 1 2 0 0 0 0 2 0 1 0 0 2 2 1 1 0 0 2 1 0 2 0 2 1 2 1 0 1 2 1 0 1 2 1 2 1 0 1 2 0 1 0 1 1 0 2 1 2 0 2 2 1 1 2 1 2 2 0 0 1 2 0 0 2 2 0 1 2 2 0 0 1 2 1 2 0 2 0 0 2 0 2 1 0 1 1 1 1 2 1 2 0 1 2 1 0 2 1 0 1 1 2 2 0 1 ...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

wrong answer expected YES, found NO [464th token]