oj.uz

Submission #992893

# Submission time Handle Problem Language Result Execution time Memory
992893 2024-06-05T08:06:38 Z danikoynov Intergalactic ship (IZhO19_xorsum) C++14
47 / 100
 2000 ms 4176 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];

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 i = 1; i <= n; i ++)
    {
        for (int bit = 0; bit < maxbit; bit ++)
        {
            for (int j = 1; j <= q; j ++)
                bt[bit][i][j] = is_affected(i, bit, j);
        }
    }

    ll ans = 0;
    for (int i = 1; i <= n; i ++)
    {
        for (int j = i; j <= n; j ++)
        {

            for (int bit_i = 0; bit_i < maxbit; bit_i ++)
            {
                for (int bit_j = 0; bit_j < maxbit; bit_j ++)
                {
                    int both = 0;
                    int ch_i = 0;
                    int ch_j = 0;
                    int neit = 0;

                    ch_i = bt[bit_i][i].count();
                    ch_j = bt[bit_j][j].count();
                    both = (bt[bit_i][i] & bt[bit_j][j]).count();
                    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;
                    }

                }
            }
        }
    }

    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 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 25 ms 2392 KB Output is correct
7 Correct 22 ms 2392 KB Output is correct
8 Correct 22 ms 2392 KB Output is correct

Subtask #3
0 / 6.0

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

Subtask #4
0 / 9.0

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

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2392 KB Output is correct
2 Correct 3 ms 2396 KB Output is correct
3 Correct 3 ms 2540 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2392 KB Output is correct
2 Correct 3 ms 2396 KB Output is correct
3 Correct 3 ms 2540 KB Output is correct
4 Correct 17 ms 2392 KB Output is correct
5 Correct 17 ms 2396 KB Output is correct
6 Correct 15 ms 2392 KB Output is correct
7 Correct 15 ms 2396 KB Output is correct

Subtask #7
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 25 ms 2392 KB Output is correct
7 Correct 22 ms 2392 KB Output is correct
8 Correct 22 ms 2392 KB Output is correct
9 Correct 3 ms 2392 KB Output is correct
10 Correct 3 ms 2396 KB Output is correct
11 Correct 3 ms 2540 KB Output is correct
12 Correct 105 ms 2540 KB Output is correct
13 Correct 110 ms 2544 KB Output is correct
14 Correct 31 ms 2396 KB Output is correct
15 Correct 46 ms 2392 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 25 ms 2392 KB Output is correct
7 Correct 22 ms 2392 KB Output is correct
8 Correct 22 ms 2392 KB Output is correct
9 Correct 3 ms 2392 KB Output is correct
10 Correct 3 ms 2396 KB Output is correct
11 Correct 3 ms 2540 KB Output is correct
12 Correct 17 ms 2392 KB Output is correct
13 Correct 17 ms 2396 KB Output is correct
14 Correct 15 ms 2392 KB Output is correct
15 Correct 15 ms 2396 KB Output is correct
16 Correct 105 ms 2540 KB Output is correct
17 Correct 110 ms 2544 KB Output is correct
18 Correct 31 ms 2396 KB Output is correct
19 Correct 46 ms 2392 KB Output is correct
20 Execution timed out 2047 ms 4176 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 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 25 ms 2392 KB Output is correct
7 Correct 22 ms 2392 KB Output is correct
8 Correct 22 ms 2392 KB Output is correct
9 Incorrect 269 ms 4144 KB Output isn't correct
10 Halted 0 ms 0 KB -