oj.uz

Submission #992934

# Submission time Handle Problem Language Result Execution time Memory
992934 2024-06-05T08:26:21 Z danikoynov Intergalactic ship (IZhO19_xorsum) C++14
53 / 100
 2000 ms 93020 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];
bitset < 310 > bt[maxbit][maxn];

int spot[(1 << maxbit) * 2][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 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);
                bt[bit][i][j] = 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;
                        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 1 ms 4696 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 6 ms 59996 KB Output is correct
4 Correct 5 ms 51752 KB Output is correct
5 Correct 6 ms 59996 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 6 ms 59996 KB Output is correct
4 Correct 5 ms 51752 KB Output is correct
5 Correct 6 ms 59996 KB Output is correct
6 Correct 26 ms 57944 KB Output is correct
7 Correct 23 ms 47720 KB Output is correct
8 Correct 27 ms 4692 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 965 ms 43348 KB Output is correct
2 Correct 117 ms 41664 KB Output is correct
3 Correct 27 ms 41564 KB Output is correct
4 Correct 22 ms 41564 KB Output is correct

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2080 ms 93020 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 33368 KB Output is correct
2 Correct 5 ms 33372 KB Output is correct
3 Correct 5 ms 33368 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 33368 KB Output is correct
2 Correct 5 ms 33372 KB Output is correct
3 Correct 5 ms 33368 KB Output is correct
4 Correct 108 ms 35416 KB Output is correct
5 Correct 108 ms 35424 KB Output is correct
6 Correct 112 ms 35420 KB Output is correct
7 Correct 107 ms 35444 KB Output is correct

Subtask #7
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 6 ms 59996 KB Output is correct
4 Correct 5 ms 51752 KB Output is correct
5 Correct 6 ms 59996 KB Output is correct
6 Correct 26 ms 57944 KB Output is correct
7 Correct 23 ms 47720 KB Output is correct
8 Correct 27 ms 4692 KB Output is correct
9 Correct 5 ms 33368 KB Output is correct
10 Correct 5 ms 33372 KB Output is correct
11 Correct 5 ms 33368 KB Output is correct
12 Correct 102 ms 68188 KB Output is correct
13 Correct 108 ms 70236 KB Output is correct
14 Correct 35 ms 70236 KB Output is correct
15 Correct 56 ms 64092 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 6 ms 59996 KB Output is correct
4 Correct 5 ms 51752 KB Output is correct
5 Correct 6 ms 59996 KB Output is correct
6 Correct 26 ms 57944 KB Output is correct
7 Correct 23 ms 47720 KB Output is correct
8 Correct 27 ms 4692 KB Output is correct
9 Correct 5 ms 33368 KB Output is correct
10 Correct 5 ms 33372 KB Output is correct
11 Correct 5 ms 33368 KB Output is correct
12 Correct 108 ms 35416 KB Output is correct
13 Correct 108 ms 35424 KB Output is correct
14 Correct 112 ms 35420 KB Output is correct
15 Correct 107 ms 35444 KB Output is correct
16 Correct 102 ms 68188 KB Output is correct
17 Correct 108 ms 70236 KB Output is correct
18 Correct 35 ms 70236 KB Output is correct
19 Correct 56 ms 64092 KB Output is correct
20 Execution timed out 2036 ms 91984 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 6 ms 59996 KB Output is correct
4 Correct 5 ms 51752 KB Output is correct
5 Correct 6 ms 59996 KB Output is correct
6 Correct 26 ms 57944 KB Output is correct
7 Correct 23 ms 47720 KB Output is correct
8 Correct 27 ms 4692 KB Output is correct
9 Correct 965 ms 43348 KB Output is correct
10 Correct 117 ms 41664 KB Output is correct
11 Correct 27 ms 41564 KB Output is correct
12 Correct 22 ms 41564 KB Output is correct
13 Execution timed out 2080 ms 93020 KB Time limit exceeded
14 Halted 0 ms 0 KB -