Submission #1156522

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156522		Faisal_Saqib	Intergalactic ship (IZhO19_xorsum)	C++20	17 / 100	2096 ms	5704 KiB

xorsum

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ull unsigned long long
#define vll vector<ll>
#define pll pair<ll,ll>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()

template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using maxpq = priority_queue<T, vector<T>, less<T>>;

void input(vll&q)
{
    for(auto&i:q)cin>>i;
}
void pyn(bool x)
{
    cout<<(x?"YES":"NO")<<endl;
}
void pYN(bool x)
{
    cout<<(x?"Yes":"No")<<endl;
}
void pAB(bool x)
{
    cout<<(x?"Alice":"Bob")<<endl;
}
const ll Q=1e5+10,mod=1e9+7,N=1e3+10;
ll a[N],b[N],pre[N];
vll query[Q];
void solve()
{
    ll n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
        ll q;
    cin>>q;
    for(int i=1;i<=q;i++)
    {
        ll l,r,x;
        cin>>l>>r>>x;
        query[i]={l,r,x};
    }
    ll ans=0;
    ll mp=(1ll<<q);
    for(int mask=0;mask<mp;mask++)
    {
        for(int i=1;i<=n;i++)b[i]=a[i];
        ll cp=mask;
        for(int i=1;i<=q;i++)
        {
            if(cp&1)
            {
                for(int p=query[i][0];p<=query[i][1];p++)
                {
                    b[p]^=query[i][2];
                }
            }
            cp>>=1;
        }
        for(int i=1;i<=n;i++)pre[i]=(b[i]+pre[i-1])%mod;
        ll tot=0,tot1=0;
        for(int i=1;i<=n;i++)
        {
            ll sq=(pre[i]*pre[i])%mod;
            ll sm=(sq*i + tot)%mod;
            sm-=(pre[i]*2ll*tot1)%mod;
            sm=((sm%mod)+mod)%mod;
            ans=(ans+sm)%mod;
            
            tot1=(tot1+pre[i])%mod;
            tot=(tot+sq)%mod;
        }
        // (pre[j]-pre[i])**2
        // (x-y) ** 2
        // (x-y) * (x-y)
        // x**2 - 2*x*y + (y**2)
        // x**2 + (y**2) - 2*x*y
    }
    cout<<ans<<endl;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--)solve();
}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 0 / 6
• Subtask 4: 0 / 9
• Subtask 5: 8 / 8
• Subtask 6: 0 / 11
• Subtask 7: 0 / 19
• Subtask 8: 0 / 30
• Subtask 9: 0 / 8