Submission #769808

#	Time	Username	Problem	Language	Result	Execution time	Memory
769808		colazcy	Intergalactic ship (IZhO19_xorsum)	C++17	53 / 100	239 ms	262144 KiB

xorsum

#include <cassert>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define let const auto
#define rep(name,beg,end) for(auto lim_##name = end,name = beg;name <= lim_##name;name++)
#define per(name,beg,end) for(auto lim_##name = end,name = beg;name >= lim_##name;name--)
#define repn(lim) for(auto REPN_lIM = lim,REPN = 1;REPN <= REPN_lIM;REPN++)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define trace() debug("line : %d, Function : %s\n",__LINE__,__FUNCTION__)
using ci = const int;
using ll = long long;
template <typename T>
constexpr bool test(const T x,ci p){return (x >> p) & 1;}

constexpr int mod = 1e9 + 7;
constexpr int add(const int a,const int b){return a + b >= mod ? a + b - mod : a + b;}
template <typename ...Args>
constexpr int add(const int a,const int b,const Args... args){return add(add(a,b),args...);}
constexpr int sub(const int a,const int b){return a >= b ? a - b : a - b + mod;}
constexpr int mul(const int a,const int b){return 1ll * a * b % mod;}
template <typename ...Args>
constexpr int mul(const int a,const int b,const Args... args){return mul(mul(a,b),args...);}
constexpr int sgn(const int x,const int p){return (p & 1) ? mod - x : x;}
template <typename T>
int qpow(int base,T b,int res = 1){
    while(b){
        if(b & 1)res = mul(res,base);
        base = mul(base,base);
        b >>= 1;
    }
    return res;
}
int inv(const int x){return qpow(x,mod - 2);}
void addeq(int &x,const int y){if((x += y) >= mod)x -= mod;}
void subeq(int &x,const int y){if((x -= y) < 0)x += mod;}
void muleq(int &x,const int y){x = mul(x,y);}

constexpr int maxn = 1003,maxq = 1e5 + 100,maxk = 7;

int val[maxn],pw[maxq],sum[maxk][maxk][2][2][maxn][maxn],n,q;
int f(ci n,ci o){
    if(n == 0)return !o;
    return pw[n - 1];
}
int query(ci k1,ci k2,ci o1,ci o2,ci xl,ci xr,ci yl,ci yr){
    if(xl > xr || yl > yr)return 0;
    let &sum = ::sum[k1][k2][o1][o2];
    return sum[xr][yr] - sum[xr][yl - 1] - sum[xl - 1][yr] + sum[xl - 1][yl - 1];
}

// std::vector<std::tuple<int,int,int>> vec;
int main(){
    // std::freopen("sample1.in","r",stdin);
    std::scanf("%d",&n);
    rep(i,1,n)std::scanf("%d",val + i);
    
    std::scanf("%d",&q);
    repn(q){
        int l,r,v; std::scanf("%d %d %d",&l,&r,&v);

        rep(k0,0,maxk - 1)
            rep(k1,0,maxk - 1)
                sum[k0][k1][test(v,k0)][test(v,k1)][l][r]++;
        
        // vec.emplace_back(l,r,v);
    }

    rep(k0,0,maxk - 1)
    rep(k1,0,maxk - 1)
    for(let o1 : {0,1})
    for(let o2 : {0,1}){
        auto &sum = ::sum[k0][k1][o1][o2];
        rep(i,1,n)
            rep(j,1,n)
                sum[i][j] = sum[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
    }

    pw[0] = 1;
    rep(i,1,q){
        pw[i] = pw[i - 1] << 1;
        if(pw[i] >= mod)pw[i] -= mod;
    }

    int ans = 0;

    rep(x,1,n)
        rep(y,x,n){
            int coef = x * (n - y + 1);
            if(x != y)coef *= 2;
            rep(k1,0,maxk - 1)
                rep(k2,0,maxk - 1){
                    int cnt[2][2]{};

                    for(let o1 : {0,1})
                    for(let o2 : {0,1}){
                        let x1 = query(k1,k2,o1,o2,1,x,y,n);
                        int x2 = query(k1,k2,o1,o2,1,x,x,n);
                        int x3 = query(k1,k2,o1,o2,1,y,y,n);
                        x2 -= x1;
                        x3 -= x1;

                        cnt[o1][o2] += x1;
                        cnt[o1][0] += x2;
                        cnt[0][o2] += x3;
                        cnt[0][0] += query(k1,k2,o1,o2,1,n,1,n) - x1 - x2 - x3;
                    }
                    
                    // for(let &[l,r,v] : vec){
                    //     if(l <= x && r >= y)cnt[test(v,k1)][test(v,k2)]++;
                    //     else if(l <= x && r >= x)cnt[test(v,k1)][0]++;
                    //     else if(l <= y && r >= y)cnt[0][test(v,k2)]++;
                    //     else cnt[0][0]++;
                    // }
                    {
                        int v = mul(coef,1 << k1,1 << k2,pw[cnt[0][0]],f(cnt[1][1],0));
                        muleq(v,f(cnt[1][0],test(val[x],k1) ^ 1));
                        muleq(v,f(cnt[0][1],test(val[y],k2) ^ 1));
                        addeq(ans,v);
                    }
                    {
                        int v = mul(coef,1 << k1,1 << k2,pw[cnt[0][0]],f(cnt[1][1],1));
                        muleq(v,f(cnt[1][0],test(val[x],k1)));
                        muleq(v,f(cnt[0][1],test(val[y],k2)));
                        addeq(ans,v);
                    }
                }
        }
    std::printf("%d\n",ans);
    return 0;
}

Compilation message (stderr)

xorsum.cpp: In function 'int main()':
xorsum.cpp:57:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |     std::scanf("%d",&n);
      |     ~~~~~~~~~~^~~~~~~~~
xorsum.cpp:58:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |     rep(i,1,n)std::scanf("%d",val + i);
      |               ~~~~~~~~~~^~~~~~~~~~~~~~
xorsum.cpp:60:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |     std::scanf("%d",&q);
      |     ~~~~~~~~~~^~~~~~~~~
xorsum.cpp:62:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         int l,r,v; std::scanf("%d %d %d",&l,&r,&v);
      |                    ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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