oj.uz

Submission #992943

# Submission time Handle Problem Language Result Execution time Memory
992943 2024-06-05T08:29:02 Z danikoynov Intergalactic ship (IZhO19_xorsum) C++14
53 / 100
 906 ms 262144 KB 
#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const ll mod = 1e9 + 7;

const int maxn = 1010;

const int maxbit = 7;
const int maxq = 1e5 + 10;

int n, q;
int a[maxn];

struct query_data
{
    int l, r, x;

    void input()
    {
        cin >> l >> r >> x;
    }
} task[maxq];

bool is_affected(int i, int bit_i, int t)
{
    if (task[t].r < i || task[t].l > i)
        return false;

    if ((task[t].x & (1 << bit_i)) == 0)
        return false;

    return true;
}

ll fac[maxq], inv[maxq];

ll power(ll base, ll st)
{
    ll res = 1;
    while(st > 0)
    {
        if (st % 2 == 1)
            res = (res * base) % mod;

        base = (base * base) % mod;
        st /= 2;
    }
    return res;
}

ll comb(ll from, ll take)
{
    if (take < 0 || take > from)
        return 0;
    return ((fac[from] * inv[take]) % mod * inv[from - take]) % mod;
}

ll pw[maxq];

const int maxmask = (1 << maxbit);
int spot[(1 << maxbit)][maxn][maxn];
int pref[(1 << maxbit)][maxn][maxn];
int ch[maxbit][maxn];

int get_both(int mask, int left, int right)
{
    int cnt = 0;
    for (int i = 1; i <= left; i ++)
    {
        for (int cur : spot[mask][i])
            if (cur >= right)
                cnt ++;
    }
    return cnt;
}
void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
        cin >> a[i];
    cin >> q;
    fac[0] = inv[0] = pw[0] = 1;
    for (int i = 1; i < max(q + 1, maxbit * 2); i ++)
    {
        pw[i] = (pw[i - 1] * 2) % mod;
    }


    for (int i = 1; i <= q; i ++)
    {

        fac[i] = (fac[i - 1] * (ll)(i)) % mod;
        inv[i] = power(fac[i], mod - 2);
    }

    for (int i = 1; i <= q; i ++)
    {
        task[i].input();

        for (int bit1 = 0; bit1 < maxbit; bit1 ++)
            for (int bit2 = bit1; bit2 < maxbit; bit2 ++)
            {
                int mask = ((1 << bit1) | (1 << bit2));
                if ((task[i].x & mask) == mask)
                {
                    spot[mask][task[i].l][task[i].r] ++;
                }
            }
    }

    for (int mask = 0; mask < (1 << maxbit); mask ++)
    {
        for (int r = 1; r <= n; r ++)
        {
            for (int l = 1; l <= r; l ++)
            {
                pref[mask][l][r] = pref[mask][l - 1][r] + spot[mask][l][r];
            }
        }
    }
    for (int i = 1; i <= n; i ++)
    {
        for (int bit = 0; bit < maxbit; bit ++)
        {

            for (int j = 1; j <= q; j ++)
            {
                ch[bit][i] += is_affected(i, bit, j);
            }
        }
    }

    ll ans = 0;

    for (int bit_i = 0; bit_i < maxbit; bit_i ++)
    {

        for (int bit_j = 0; bit_j < maxbit; bit_j ++)
        {
            int both = 0;
            int mask =((1 << bit_i) | (1 << bit_j));
            for (int i = 1; i <= n; i ++)
            {
                for (int j = i; j <= n; j ++)
                    both += spot[mask][i][j];

                if (i > 1)
                {
                    for (int j = 1; j < i; j ++)
                        both -= spot[mask][j][i - 1];
                }
                int rem = 0;
                for (int j = i; j <= n; j ++)
                {

                    ///int both = 0;
                    int ch_i = 0;
                    int ch_j = 0;
                    int neit = 0;

                    if (j > i)
                    {
                        int l = 0;
                        l = pref[mask][i][j - 1];
                        //for (int d = 1; d <= i; d ++)
                          //  l += spot[mask][d][j - 1];
                        rem += l;
                        both -= l;
                    }
                    //ch_i = bt[bit_i][i].count();
                    //ch_j = bt[bit_j][j].count();

                    ch_i = ch[bit_i][i];
                    ch_j = ch[bit_j][j];
                    ///for (int ii = 1; ii <= i; ii ++)
                       // for (int jj = j; jj <= n; jj ++)
                        //both += spot[mask][ii][jj];
                    ///both = get_both(((1 << bit_i) | (1 << bit_j)), i, j);
                    //both = (bt[bit_i][i] & bt[bit_j][j]).count();
                    //assert(both <= get_both(((1 << bit_i) | (1 << bit_j)), i, j));
                    ch_i -= both;
                    ch_j -= both;
                    neit = q - both - ch_i - ch_j;
                    /**for (int t = 1; t <= q; t ++)
                    {
                        bool af_i = is_affected(i, bit_i, t), af_j = is_affected(j, bit_j, t);
                        if (af_i == false && af_j == false)
                            neit ++;
                        else if (af_i == true && af_j == false)
                            ch_i ++;
                        else if (af_i == false && af_j == true)
                            ch_j ++;
                        else if (af_i == true && af_j == true)
                            both ++;
                    }*/

                    int val_i = ((a[i] & (1 << bit_i)) > 0);
                    int val_j = ((a[j] & (1 << bit_j)) > 0);

                    ll res = 0;
                    for (int d_i = 0; d_i < 2; d_i ++)
                        for (int d_j = 0; d_j < 2; d_j ++)
                            for (int b = 0; b < 2; b ++)
                            {
                                if ((val_i + d_i + b) % 2 == 0 ||
                                        (val_j + d_j + b) % 2 == 0)
                                    continue;

                                ll way_i = 0;
                                ll way_j = 0;
                                ll way_b = 0;
                                for (int l = d_i; l <= ch_i;  l += 2)
                                {
                                    way_i += comb(ch_i, l);
                                    if (way_i >= mod)
                                        way_i -= mod;
                                }
                                for (int l = d_j; l <= ch_j; l += 2)
                                {
                                    way_j += comb(ch_j, l);
                                    if (way_j >= mod)
                                        way_j -= mod;
                                }
                                for (int l = b; l <= both; l += 2)
                                {
                                    way_b += comb(both, l);
                                    if (way_b >= mod)
                                        way_b -= mod;
                                }
                                ///if ((a[i] & (1 << bit_i)) > 0 && (a[j] & (1 << bit_j)) > 0)
                                {
                                    ///cout << "ways " << way_i << " " << way_j << " " << way_b << endl;
                                }

                                ll ways = ((way_i * way_j) % mod * way_b) % mod;
                                res = res + ways;
                                if (res >= mod)
                                    res -= mod;
                            }



                    res = (res * (pw[bit_i + bit_j])) % mod;
                    res = (res * pw[neit]) % mod;
                    res = (res * (ll)(i) * (ll)(n - j + 1)) % mod;
                    if (i != j)
                        res = (res * 2) % mod;
                    ans += res;
                    if (ans >= mod)
                        ans -= mod;
                    ///if ((a[i] & (1 << bit_i)) > 0 && (a[j] & (1 << bit_j)) > 0)
                    {
                        ///cout << i << " " << j << " " << bit_i << " " << bit_j << " " << res << endl;
                        ///cout << pw[bit_i + bit_j] << " " << (i * (n - i + 1)) << endl;
                        ///cout << ans << endl;
                    }

                }
                both += rem;
            }
        }
    }

    cout << ans << endl;
}

int main()
{
    speed();
    solve();
    return 0;
}
/**
2
1 3
2
1 2 2
1 1 1

*/

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 3 ms 8028 KB Output is correct
3 Correct 9 ms 72024 KB Output is correct
4 Correct 9 ms 61788 KB Output is correct
5 Correct 10 ms 69980 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 3 ms 8028 KB Output is correct
3 Correct 9 ms 72024 KB Output is correct
4 Correct 9 ms 61788 KB Output is correct
5 Correct 10 ms 69980 KB Output is correct
6 Correct 48 ms 122460 KB Output is correct
7 Correct 49 ms 121684 KB Output is correct
8 Correct 41 ms 98896 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 906 ms 122616 KB Output is correct
2 Correct 127 ms 121104 KB Output is correct
3 Correct 46 ms 122972 KB Output is correct
4 Correct 42 ms 122716 KB Output is correct

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 128 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 16 ms 63324 KB Output is correct
2 Correct 13 ms 61272 KB Output is correct
3 Correct 14 ms 63324 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 63324 KB Output is correct
2 Correct 13 ms 61272 KB Output is correct
3 Correct 14 ms 63324 KB Output is correct
4 Correct 117 ms 63580 KB Output is correct
5 Correct 117 ms 63576 KB Output is correct
6 Correct 120 ms 63580 KB Output is correct
7 Correct 117 ms 63580 KB Output is correct

Subtask #7
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 3 ms 8028 KB Output is correct
3 Correct 9 ms 72024 KB Output is correct
4 Correct 9 ms 61788 KB Output is correct
5 Correct 10 ms 69980 KB Output is correct
6 Correct 48 ms 122460 KB Output is correct
7 Correct 49 ms 121684 KB Output is correct
8 Correct 41 ms 98896 KB Output is correct
9 Correct 16 ms 63324 KB Output is correct
10 Correct 13 ms 61272 KB Output is correct
11 Correct 14 ms 63324 KB Output is correct
12 Correct 123 ms 125592 KB Output is correct
13 Correct 126 ms 123476 KB Output is correct
14 Correct 51 ms 125272 KB Output is correct
15 Correct 69 ms 123484 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 3 ms 8028 KB Output is correct
3 Correct 9 ms 72024 KB Output is correct
4 Correct 9 ms 61788 KB Output is correct
5 Correct 10 ms 69980 KB Output is correct
6 Correct 48 ms 122460 KB Output is correct
7 Correct 49 ms 121684 KB Output is correct
8 Correct 41 ms 98896 KB Output is correct
9 Correct 16 ms 63324 KB Output is correct
10 Correct 13 ms 61272 KB Output is correct
11 Correct 14 ms 63324 KB Output is correct
12 Correct 117 ms 63580 KB Output is correct
13 Correct 117 ms 63576 KB Output is correct
14 Correct 120 ms 63580 KB Output is correct
15 Correct 117 ms 63580 KB Output is correct
16 Correct 123 ms 125592 KB Output is correct
17 Correct 126 ms 123476 KB Output is correct
18 Correct 51 ms 125272 KB Output is correct
19 Correct 69 ms 123484 KB Output is correct
20 Runtime error 142 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 2 ms 6492 KB Output is correct
2 Correct 3 ms 8028 KB Output is correct
3 Correct 9 ms 72024 KB Output is correct
4 Correct 9 ms 61788 KB Output is correct
5 Correct 10 ms 69980 KB Output is correct
6 Correct 48 ms 122460 KB Output is correct
7 Correct 49 ms 121684 KB Output is correct
8 Correct 41 ms 98896 KB Output is correct
9 Correct 906 ms 122616 KB Output is correct
10 Correct 127 ms 121104 KB Output is correct
11 Correct 46 ms 122972 KB Output is correct
12 Correct 42 ms 122716 KB Output is correct
13 Runtime error 128 ms 262144 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -