oj.uz

Submission #992857

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

    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;

                    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 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2508 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 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2508 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 18 ms 2680 KB Output is correct
7 Correct 13 ms 2396 KB Output is correct
8 Correct 19 ms 2528 KB Output is correct

Subtask #3
0 / 6.0

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

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2073 ms 2396 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 2396 KB Output is correct
2 Correct 5 ms 2396 KB Output is correct
3 Correct 3 ms 2396 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2396 KB Output is correct
2 Correct 5 ms 2396 KB Output is correct
3 Correct 3 ms 2396 KB Output is correct
4 Correct 870 ms 2652 KB Output is correct
5 Correct 875 ms 2648 KB Output is correct
6 Correct 859 ms 2652 KB Output is correct
7 Correct 928 ms 2652 KB Output is correct

Subtask #7
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2508 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 18 ms 2680 KB Output is correct
7 Correct 13 ms 2396 KB Output is correct
8 Correct 19 ms 2528 KB Output is correct
9 Correct 3 ms 2396 KB Output is correct
10 Correct 5 ms 2396 KB Output is correct
11 Correct 3 ms 2396 KB Output is correct
12 Correct 356 ms 2504 KB Output is correct
13 Correct 396 ms 2652 KB Output is correct
14 Correct 153 ms 2516 KB Output is correct
15 Correct 220 ms 2504 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2508 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 18 ms 2680 KB Output is correct
7 Correct 13 ms 2396 KB Output is correct
8 Correct 19 ms 2528 KB Output is correct
9 Correct 3 ms 2396 KB Output is correct
10 Correct 5 ms 2396 KB Output is correct
11 Correct 3 ms 2396 KB Output is correct
12 Correct 870 ms 2652 KB Output is correct
13 Correct 875 ms 2648 KB Output is correct
14 Correct 859 ms 2652 KB Output is correct
15 Correct 928 ms 2652 KB Output is correct
16 Correct 356 ms 2504 KB Output is correct
17 Correct 396 ms 2652 KB Output is correct
18 Correct 153 ms 2516 KB Output is correct
19 Correct 220 ms 2504 KB Output is correct
20 Execution timed out 2047 ms 4956 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 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2508 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 18 ms 2680 KB Output is correct
7 Correct 13 ms 2396 KB Output is correct
8 Correct 19 ms 2528 KB Output is correct
9 Execution timed out 2052 ms 3840 KB Time limit exceeded
10 Halted 0 ms 0 KB -