oj.uz

Submission #769807

# Submission time Handle Problem Language Result Execution time Memory
769807 2023-06-30T09:23:47 Z colazcy Intergalactic ship (IZhO19_xorsum) C++17
53 / 100
 552 ms 18676 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 = 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
4.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 Correct 2 ms 1748 KB Output is correct
4 Correct 1 ms 1748 KB Output is correct
5 Correct 1 ms 1700 KB Output is correct

Subtask #2
5.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 Correct 2 ms 1748 KB Output is correct
4 Correct 1 ms 1748 KB Output is correct
5 Correct 1 ms 1700 KB Output is correct
6 Correct 47 ms 8408 KB Output is correct
7 Correct 48 ms 8416 KB Output is correct
8 Correct 41 ms 8404 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 8764 KB Output is correct
2 Correct 43 ms 8532 KB Output is correct
3 Correct 42 ms 8420 KB Output is correct
4 Correct 42 ms 8328 KB Output is correct

Subtask #4
0 / 9.0

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

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3284 KB Output is correct
2 Correct 6 ms 3316 KB Output is correct
3 Correct 5 ms 3392 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3284 KB Output is correct
2 Correct 6 ms 3316 KB Output is correct
3 Correct 5 ms 3392 KB Output is correct
4 Correct 6 ms 3460 KB Output is correct
5 Correct 6 ms 3452 KB Output is correct
6 Correct 6 ms 3412 KB Output is correct
7 Correct 6 ms 3412 KB Output is correct

Subtask #7
19.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 Correct 2 ms 1748 KB Output is correct
4 Correct 1 ms 1748 KB Output is correct
5 Correct 1 ms 1700 KB Output is correct
6 Correct 47 ms 8408 KB Output is correct
7 Correct 48 ms 8416 KB Output is correct
8 Correct 41 ms 8404 KB Output is correct
9 Correct 5 ms 3284 KB Output is correct
10 Correct 6 ms 3316 KB Output is correct
11 Correct 5 ms 3392 KB Output is correct
12 Correct 53 ms 8524 KB Output is correct
13 Correct 41 ms 8412 KB Output is correct
14 Correct 40 ms 8404 KB Output is correct
15 Correct 41 ms 8404 KB Output is correct

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 Correct 2 ms 1748 KB Output is correct
4 Correct 1 ms 1748 KB Output is correct
5 Correct 1 ms 1700 KB Output is correct
6 Correct 47 ms 8408 KB Output is correct
7 Correct 48 ms 8416 KB Output is correct
8 Correct 41 ms 8404 KB Output is correct
9 Correct 5 ms 3284 KB Output is correct
10 Correct 6 ms 3316 KB Output is correct
11 Correct 5 ms 3392 KB Output is correct
12 Correct 6 ms 3460 KB Output is correct
13 Correct 6 ms 3452 KB Output is correct
14 Correct 6 ms 3412 KB Output is correct
15 Correct 6 ms 3412 KB Output is correct
16 Correct 53 ms 8524 KB Output is correct
17 Correct 41 ms 8412 KB Output is correct
18 Correct 40 ms 8404 KB Output is correct
19 Correct 41 ms 8404 KB Output is correct
20 Runtime error 181 ms 18676 KB Execution killed with signal 11
21 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 Correct 2 ms 1748 KB Output is correct
4 Correct 1 ms 1748 KB Output is correct
5 Correct 1 ms 1700 KB Output is correct
6 Correct 47 ms 8408 KB Output is correct
7 Correct 48 ms 8416 KB Output is correct
8 Correct 41 ms 8404 KB Output is correct
9 Correct 73 ms 8764 KB Output is correct
10 Correct 43 ms 8532 KB Output is correct
11 Correct 42 ms 8420 KB Output is correct
12 Correct 42 ms 8328 KB Output is correct
13 Runtime error 552 ms 17468 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -