oj.uz

Submission #993008

# Submission time Handle Problem Language Result Execution time Memory
993008 2024-06-05T08:56:01 Z danikoynov Intergalactic ship (IZhO19_xorsum) C++14
92 / 100
 2000 ms 231248 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[maxbit * maxbit][maxn][maxn];
int pref[maxbit * maxbit][maxn][maxn];
int ch[maxbit][maxn];
int mask_to_idx[(1 << maxbit)];
int idx_to_mask[maxbit * maxbit];

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);
    }

    int cnt = 0;
    for (int bit1 = 0; bit1 < maxbit; bit1 ++)
        for (int bit2 = bit1; bit2 < maxbit; bit2 ++)
        {
            int mask = ((1 << bit1) | (1 << bit2));
            cnt ++;
            mask_to_idx[mask] = cnt;
            idx_to_mask[cnt] = mask;
        }
    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_to_idx[mask]][task[i].l][task[i].r] ++;
                }
            }
    }

    for (int mask = 0; mask < (1 << maxbit); mask ++)
    {
        int idx = mask_to_idx[mask];
        for (int r = 1; r <= n; r ++)
        {
            for (int l = 1; l <= r; l ++)
            {
                pref[idx][l][r] = pref[idx][l - 1][r] + spot[idx][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)), idx = mask_to_idx[mask];
            for (int i = 1; i <= n; i ++)
            {
                for (int j = i; j <= n; j ++)
                    both += spot[idx][i][j];

                if (i > 1)
                {
                    for (int j = 1; j < i; j ++)
                        both -= spot[idx][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[idx][i][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];

                    ch_i -= both;
                    ch_j -= both;
                    neit = q - both - ch_i - ch_j;


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

                    ll res = 0;

                    for (int b = 0; b < 2; b ++)
                    {
                        int d_i = 0;
                        if ((val_i + d_i + b) % 2 == 0)
                            d_i = 1;
                        int d_j = 0;
                        if ((val_j + d_j + b) % 2 == 0)
                            d_j = 1;



                        ll way_i = 0;
                        ll way_j = 0;
                        ll way_b = 0;
                        if (ch_i % 2 == 0)
                        {

                            if (ch_i == 0)
                            {
                                if (d_i == 0)
                                    way_i = 1;
                            }
                            else
                                way_i = pw[ch_i - 1];

                        }
                        else
                        {
                            way_i = pw[ch_i - 1];
                        }

                        if (ch_j % 2 == 0)
                        {

                            if (ch_j == 0)
                            {
                                if (d_j == 0)
                                    way_j = 1;
                            }
                            else
                                way_j = pw[ch_j - 1];

                        }
                        else
                        {
                            way_j = pw[ch_j - 1];
                        }


                        if (both % 2 == 0)
                        {

                            if (both == 0)
                            {
                                if (b == 0)
                                    way_b = 1;
                            }
                            else
                                way_b = pw[both - 1];

                        }
                        else
                        {
                            way_b = pw[both - 1];
                        }


                        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 7000 KB Output is correct
2 Correct 1 ms 5208 KB Output is correct
3 Correct 6 ms 63068 KB Output is correct
4 Correct 6 ms 55120 KB Output is correct
5 Correct 6 ms 63068 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7000 KB Output is correct
2 Correct 1 ms 5208 KB Output is correct
3 Correct 6 ms 63068 KB Output is correct
4 Correct 6 ms 55120 KB Output is correct
5 Correct 6 ms 63068 KB Output is correct
6 Correct 17 ms 85084 KB Output is correct
7 Correct 15 ms 72540 KB Output is correct
8 Correct 12 ms 29532 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 63056 KB Output is correct
2 Correct 33 ms 62296 KB Output is correct
3 Correct 16 ms 62484 KB Output is correct
4 Correct 14 ms 60252 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 611 ms 195784 KB Output is correct
2 Correct 604 ms 201296 KB Output is correct
3 Correct 604 ms 198364 KB Output is correct
4 Correct 586 ms 197716 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 42840 KB Output is correct
2 Correct 5 ms 42844 KB Output is correct
3 Correct 6 ms 42844 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 42840 KB Output is correct
2 Correct 5 ms 42844 KB Output is correct
3 Correct 6 ms 42844 KB Output is correct
4 Correct 9 ms 42844 KB Output is correct
5 Correct 9 ms 43080 KB Output is correct
6 Correct 10 ms 42844 KB Output is correct
7 Correct 9 ms 42844 KB Output is correct

Subtask #7
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7000 KB Output is correct
2 Correct 1 ms 5208 KB Output is correct
3 Correct 6 ms 63068 KB Output is correct
4 Correct 6 ms 55120 KB Output is correct
5 Correct 6 ms 63068 KB Output is correct
6 Correct 17 ms 85084 KB Output is correct
7 Correct 15 ms 72540 KB Output is correct
8 Correct 12 ms 29532 KB Output is correct
9 Correct 5 ms 42840 KB Output is correct
10 Correct 5 ms 42844 KB Output is correct
11 Correct 6 ms 42844 KB Output is correct
12 Correct 21 ms 95408 KB Output is correct
13 Correct 20 ms 95576 KB Output is correct
14 Correct 19 ms 93508 KB Output is correct
15 Correct 19 ms 93428 KB Output is correct

Subtask #8
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7000 KB Output is correct
2 Correct 1 ms 5208 KB Output is correct
3 Correct 6 ms 63068 KB Output is correct
4 Correct 6 ms 55120 KB Output is correct
5 Correct 6 ms 63068 KB Output is correct
6 Correct 17 ms 85084 KB Output is correct
7 Correct 15 ms 72540 KB Output is correct
8 Correct 12 ms 29532 KB Output is correct
9 Correct 5 ms 42840 KB Output is correct
10 Correct 5 ms 42844 KB Output is correct
11 Correct 6 ms 42844 KB Output is correct
12 Correct 9 ms 42844 KB Output is correct
13 Correct 9 ms 43080 KB Output is correct
14 Correct 10 ms 42844 KB Output is correct
15 Correct 9 ms 42844 KB Output is correct
16 Correct 21 ms 95408 KB Output is correct
17 Correct 20 ms 95576 KB Output is correct
18 Correct 19 ms 93508 KB Output is correct
19 Correct 19 ms 93428 KB Output is correct
20 Correct 1497 ms 146768 KB Output is correct
21 Correct 1034 ms 147540 KB Output is correct
22 Correct 1452 ms 148304 KB Output is correct

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7000 KB Output is correct
2 Correct 1 ms 5208 KB Output is correct
3 Correct 6 ms 63068 KB Output is correct
4 Correct 6 ms 55120 KB Output is correct
5 Correct 6 ms 63068 KB Output is correct
6 Correct 17 ms 85084 KB Output is correct
7 Correct 15 ms 72540 KB Output is correct
8 Correct 12 ms 29532 KB Output is correct
9 Correct 216 ms 63056 KB Output is correct
10 Correct 33 ms 62296 KB Output is correct
11 Correct 16 ms 62484 KB Output is correct
12 Correct 14 ms 60252 KB Output is correct
13 Correct 611 ms 195784 KB Output is correct
14 Correct 604 ms 201296 KB Output is correct
15 Correct 604 ms 198364 KB Output is correct
16 Correct 586 ms 197716 KB Output is correct
17 Correct 5 ms 42840 KB Output is correct
18 Correct 5 ms 42844 KB Output is correct
19 Correct 6 ms 42844 KB Output is correct
20 Correct 9 ms 42844 KB Output is correct
21 Correct 9 ms 43080 KB Output is correct
22 Correct 10 ms 42844 KB Output is correct
23 Correct 9 ms 42844 KB Output is correct
24 Correct 21 ms 95408 KB Output is correct
25 Correct 20 ms 95576 KB Output is correct
26 Correct 19 ms 93508 KB Output is correct
27 Correct 19 ms 93428 KB Output is correct
28 Correct 1497 ms 146768 KB Output is correct
29 Correct 1034 ms 147540 KB Output is correct
30 Correct 1452 ms 148304 KB Output is correct
31 Execution timed out 2025 ms 231248 KB Time limit exceeded
32 Halted 0 ms 0 KB -