Submission #441163

#	Time	Username	Problem	Language	Result	Execution time	Memory
441163		leaked	Intergalactic ship (IZhO19_xorsum)	C++14	92 / 100	2079 ms	7588 KiB

xorsum

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC opimize(-O3)
//#pragma GCC opimize(Ofast)
//#pragma GCC opimize(unroll-loops)
//#pragma GCC target("avx,avx2,popcnt,sse,sse2,sse3,sse4,abm,tune=native")
#define m_p make_pair
#define vec vector
#define all(x) x.begin(),x.end()
#define pb push_back
#define sz(x) (int)x.size()
#define pw(x) (1<<x)
#define f first
#define s second

using namespace std;
using namespace __gnu_pbds;
typedef long double ld;
typedef pair<int,int> pii;
const int N=1e3+2;
const int Q=1e5+3;
const int M=1e9+7;
//int pref[4][N][N];
int prec[2][Q];
int p2[Q];
vec<array<int,3>>go[4];
int mult(int a,int b){
    return 1ll*a*b%M;
}
void add(int &a,int b){
    a+=b;
    if(a>=M) a-=M;
    else if(a<0) a+=M;
}
struct _2d{
    int pref[N][N];
    void clr(){
        for(int i=0;i<N;i++){
            fill(pref[i],pref[i]+N,0);
        }
    }
    void build(){
        for(int i=0;i<N;i++){
            for(int j=1;j<N;j++){
                pref[i][j]+=pref[i][j-1];
            }
        }
        for(int i=1;i<N;i++){
            for(int j=0;j<N;j++){
                pref[i][j]+=pref[i-1][j];
            }
        }
    }
    int get(int x1,int x2,int y1,int y2){
        if(x1>x2) return 0;
        int w=pref[x2][y2];
        if(x1) w-=pref[x1-1][y2];
        if(y1) w-=pref[x2][y1-1];
        if(x1 && y1) w+=pref[x1-1][y1-1];
        return w;
    }
}st;
struct _1d{
    int pref[N];
    void clr(){
        for(int i=0;i<N;i++) pref[i]=0;
    }
    void build(){
        for(int i=1;i<N;i++){
            pref[i]+=pref[i-1];
        }
    }
    int get(int x){
        return pref[x];
    }
}lol[3];
signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    p2[0]=1;for(int i=1;i<Q;i++) p2[i]=mult(p2[i-1],2);
    vec<int>a(n);
    for(auto &z : a)
        cin>>z;
    int q;
    cin>>q;
    vec<int>l(q),r(q),x(q);
    for(int i=0;i<q;i++){
        cin>>l[i]>>r[i]>>x[i];--l[i];--r[i];
    }
    for(int i=0;i<4;i++){
        for(int f=0;f<2;f++){
            for(int j=0;j<2;j++){
                for(int k=0;k<2;k++){
                    int msk=i;
                    if(f) msk^=1;
                    if(j) msk^=2;
                    if(k) msk^=3;
                    if(msk==3){
                        go[i].pb({f,j,k});
                    }
                }
            }
        }
    }
    prec[0][0]=1;
    for(int i=0;i<=q;i++){
        for(int cr=0;cr<2;cr++){
            add(prec[cr][i+1],prec[cr][i]);
            add(prec[cr^1][i+1],prec[cr][i]);
        }
    }
    auto stupid=[&](int b1,int b2,int i,int j){
        vec<int>cnt(4,0);
        for(int t=0;t<q;t++){
            if(l[t]<=i && r[t]>=j){
                if((x[t]&pw(b1)) && (x[t]&pw(b2))) cnt[3]++;
                else if(x[t]&pw(b1)) cnt[1]++;
                else if(x[t]&pw(b2)) cnt[2]++;
                else cnt[0]++;
            }
            else if(r[t]<j && l[t]<=i && r[t]>=i){
                if(x[t]&pw(b1)) cnt[1]++;
                else cnt[0]++;
            }
            else if(l[t]>i && l[t]<=j && r[t]>=j){
                if(x[t]&pw(b2)) cnt[2]++;
                else cnt[0]++;
            }
            else{
                cnt[0]++;
            }
        }
        return cnt;
    };
    int ans=0;
    for(int b1=0;b1<7;b1++){
        for(int b2=0;b2<7;b2++){
            st.clr();
            for(int j=1;j<=2;j++) lol[j].clr();
            for(int i=0;i<q;i++){
                int f=(x[i]>>b1)&1;
                int s=(x[i]>>b2)&1;
                s<<=1;s+=f;
                if(s==3) st.pref[l[i]][r[i]]++;
                if(s&1) lol[1].pref[l[i]]++,lol[1].pref[r[i]+1]--;
                if(s&2) lol[2].pref[r[i]+1]--,lol[2].pref[l[i]]++;
            }
            st.build();
            for(int i=1;i<=2;i++) lol[i].build();
            vec<int>cnt(4,0);
            for(int i=0;i<n;i++){
                for(int j=i;j<n;j++){
                    int start=((a[i]>>b1)&1)+(((a[j]>>b2)&1)<<1);
                    cnt[3]=st.get(0,i,j,n-1);
                    cnt[1]=lol[1].get(i)-cnt[3];
                    cnt[2]=+lol[2].get(j)-cnt[3];
                    cnt[0]=(q-cnt[1]-cnt[2]-cnt[3]);
                    for(auto &z : go[start]){
                        int w=p2[cnt[0]];
                        w=mult(w,mult(prec[z[0]][cnt[1]],prec[z[1]][cnt[2]]));
                        w=mult(w,prec[z[2]][cnt[3]]);
                        if(i!=j) w=mult(2,w);
                        w=mult(n-j,mult(i+1,w));
                        add(ans,mult(w,p2[b1+b2]));
                    }
                }
            }
        }
    }
    cout<<ans;
    return 0;
}
/*
5
1 2 3 4 5
1
1 4 3

*/

Compilation message (stderr)

xorsum.cpp: In function 'int main()':
xorsum.cpp:115:10: warning: variable 'stupid' set but not used [-Wunused-but-set-variable]
  115 |     auto stupid=[&](int b1,int b2,int i,int j){
      |          ^~~~~~

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