/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 7ms 10.328 MiB
#2 Accepted 7ms 11.277 MiB
#3 Accepted 7ms 10.316 MiB
#4 Accepted 7ms 11.254 MiB
#5 Accepted 8ms 11.02 MiB
#6 Accepted 7ms 11.105 MiB
#7 Wrong Answer 582ms 45.418 MiB
#8 Wrong Answer 503ms 45.211 MiB

Code

/*
 *   Copyright (c) 2025 Emon Thakur
 *   All rights reserved.
 */
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll mod = 1e9+7;
ll p2[100005],a[100005],n,q;
vector<ll> sg[400000];

int on(int x,int i) {return (x&(1<<i))?1:0;}
void comb(int node)
{
    sg[node].resize(21);
    for(int i=0;i<=20;i++) sg[node][i] = sg[node*2][i]+sg[node*2+1][i];
}
void buildsg(int node,int start,int end)
{
    if(start==end)
    {
        sg[node].resize(21);
        for(int i=0;i<=20;i++) sg[node][i] = on(a[start],i);
        return;
    }
    int mid = (start+end)/2;
    buildsg(node*2,start,mid);
    buildsg(node*2+1,mid+1,end);
    comb(node);
}

void update(int node,int start,int end,int ind,int x)
{
    if(start==end)
    {
        for(int i=0;i<=20;i++) sg[node][i] ^= on(x,i);
        return;
    }
    int mid = (start+end)/2;
    if(ind <= mid) update(node*2,start,mid,ind,x);
    else update(node*2+1,mid+1,end,ind,x);
    comb(node);
}

vector<ll> query(int node,int start,int end,int l,int r)
{
    vector<ll> v(21);
    if(l>end || r<start) return v;
    if(l<=start && r>=end) return sg[node];
    int mid = (start+end)/2;
    auto v1 = query(node*2,start,mid,l,r);
    auto v2 =  query(node*2+1,mid+1,end,l,r);
    for(int i=0;i<=20;i++) v1[i] += v2[i];
    return v1;
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr);
    p2[0] = 1;
    for(int i=1;i<=100000;i++) p2[i] = (p2[i-1]*2ll)%mod;

    cin >> n >> q;
    for(int i=1;i<=n;i++) cin >> a[i];
    buildsg(1,1,n);
    int type,ind,x,l,r;
    while(q--)
    {
        cin >> type;
        if(type==1)
        {
            cin >> ind >> x;
            update(1,1,n,ind,x);
        }else
        {
            cin >> l >> r;
            auto v = query(1,1,n,l,r);
            ll ans = 0,zero, one;
            for(ll i=0;i<=20;i++) 
            {
                if(v[i]==0) continue;
                zero = r-l+1-v[i];
                one = v[i];
                ans += (1<<i) * p2[one-1] * p2[zero];
                ans %= mod;
            }
            cout<<ans<<'\n';
        }
    }
}

Information

Submit By
Type
Submission
Problem
P1183 The Sorcerer’s Subsequence Sum
Language
C++17 (G++ 13.2.0)
Submit At
2025-03-22 08:49:18
Judged At
2025-03-22 08:49:18
Judged By
Score
6
Total Time
582ms
Peak Memory
45.418 MiB