oj.uz

Submission #769803

# Submission time Handle Problem Language Result Execution time Memory
769803 2023-06-30T09:22:44 Z colazcy Intergalactic ship (IZhO19_xorsum) C++17
0 / 100
 546 ms 17484 KB 
#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 = 998244353;
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 = 103,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

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
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct
3 Incorrect 1 ms 1704 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct
3 Incorrect 1 ms 1704 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 68 ms 9476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 546 ms 17484 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 3284 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 3284 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct
3 Incorrect 1 ms 1704 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct
3 Incorrect 1 ms 1704 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct
3 Incorrect 1 ms 1704 KB Output isn't correct
4 Halted 0 ms 0 KB -