oj.uz

Submission #769808

# Submission time Handle Problem Language Result Execution time Memory
769808 2023-06-30T09:24:11 Z colazcy Intergalactic ship (IZhO19_xorsum) C++17
53 / 100
 239 ms 262144 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 = 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

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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2516 KB Output is correct
2 Correct 4 ms 4820 KB Output is correct
3 Correct 7 ms 8732 KB Output is correct
4 Correct 7 ms 8788 KB Output is correct
5 Correct 7 ms 8780 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2516 KB Output is correct
2 Correct 4 ms 4820 KB Output is correct
3 Correct 7 ms 8732 KB Output is correct
4 Correct 7 ms 8788 KB Output is correct
5 Correct 7 ms 8780 KB Output is correct
6 Correct 99 ms 78092 KB Output is correct
7 Correct 113 ms 78088 KB Output is correct
8 Correct 97 ms 78084 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 78428 KB Output is correct
2 Correct 108 ms 78112 KB Output is correct
3 Correct 97 ms 78088 KB Output is correct
4 Correct 100 ms 78012 KB Output is correct

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 239 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 24148 KB Output is correct
2 Correct 19 ms 24172 KB Output is correct
3 Correct 25 ms 24156 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 24148 KB Output is correct
2 Correct 19 ms 24172 KB Output is correct
3 Correct 25 ms 24156 KB Output is correct
4 Correct 21 ms 24148 KB Output is correct
5 Correct 21 ms 24148 KB Output is correct
6 Correct 18 ms 24168 KB Output is correct
7 Correct 19 ms 24192 KB Output is correct

Subtask #7
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2516 KB Output is correct
2 Correct 4 ms 4820 KB Output is correct
3 Correct 7 ms 8732 KB Output is correct
4 Correct 7 ms 8788 KB Output is correct
5 Correct 7 ms 8780 KB Output is correct
6 Correct 99 ms 78092 KB Output is correct
7 Correct 113 ms 78088 KB Output is correct
8 Correct 97 ms 78084 KB Output is correct
9 Correct 18 ms 24148 KB Output is correct
10 Correct 19 ms 24172 KB Output is correct
11 Correct 25 ms 24156 KB Output is correct
12 Correct 95 ms 78096 KB Output is correct
13 Correct 105 ms 78036 KB Output is correct
14 Correct 120 ms 78092 KB Output is correct
15 Correct 105 ms 78088 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2516 KB Output is correct
2 Correct 4 ms 4820 KB Output is correct
3 Correct 7 ms 8732 KB Output is correct
4 Correct 7 ms 8788 KB Output is correct
5 Correct 7 ms 8780 KB Output is correct
6 Correct 99 ms 78092 KB Output is correct
7 Correct 113 ms 78088 KB Output is correct
8 Correct 97 ms 78084 KB Output is correct
9 Correct 18 ms 24148 KB Output is correct
10 Correct 19 ms 24172 KB Output is correct
11 Correct 25 ms 24156 KB Output is correct
12 Correct 21 ms 24148 KB Output is correct
13 Correct 21 ms 24148 KB Output is correct
14 Correct 18 ms 24168 KB Output is correct
15 Correct 19 ms 24192 KB Output is correct
16 Correct 95 ms 78096 KB Output is correct
17 Correct 105 ms 78036 KB Output is correct
18 Correct 120 ms 78092 KB Output is correct
19 Correct 105 ms 78088 KB Output is correct
20 Runtime error 79 ms 262144 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2516 KB Output is correct
2 Correct 4 ms 4820 KB Output is correct
3 Correct 7 ms 8732 KB Output is correct
4 Correct 7 ms 8788 KB Output is correct
5 Correct 7 ms 8780 KB Output is correct
6 Correct 99 ms 78092 KB Output is correct
7 Correct 113 ms 78088 KB Output is correct
8 Correct 97 ms 78084 KB Output is correct
9 Correct 166 ms 78428 KB Output is correct
10 Correct 108 ms 78112 KB Output is correct
11 Correct 97 ms 78088 KB Output is correct
12 Correct 100 ms 78012 KB Output is correct
13 Runtime error 239 ms 262144 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -