oj.uz

Submission #993007

# Submission time Handle Problem Language Result Execution time Memory
993007 2024-06-05T08:54:33 Z danikoynov Intergalactic ship (IZhO19_xorsum) C++14
92 / 100
 2000 ms 232020 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 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;
                                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 1 ms 7004 KB Output is correct
2 Correct 1 ms 5212 KB Output is correct
3 Correct 7 ms 63068 KB Output is correct
4 Correct 6 ms 54884 KB Output is correct
5 Correct 7 ms 63064 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7004 KB Output is correct
2 Correct 1 ms 5212 KB Output is correct
3 Correct 7 ms 63068 KB Output is correct
4 Correct 6 ms 54884 KB Output is correct
5 Correct 7 ms 63064 KB Output is correct
6 Correct 19 ms 86872 KB Output is correct
7 Correct 19 ms 72536 KB Output is correct
8 Correct 14 ms 29532 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 63060 KB Output is correct
2 Correct 33 ms 62300 KB Output is correct
3 Correct 19 ms 62300 KB Output is correct
4 Correct 19 ms 60248 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 827 ms 199540 KB Output is correct
2 Correct 896 ms 201628 KB Output is correct
3 Correct 840 ms 196180 KB Output is correct
4 Correct 814 ms 193616 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 42844 KB Output is correct
2 Correct 6 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 7 ms 42844 KB Output is correct
2 Correct 6 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 10 ms 42896 KB Output is correct
6 Correct 10 ms 42840 KB Output is correct
7 Correct 12 ms 43032 KB Output is correct

Subtask #7
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7004 KB Output is correct
2 Correct 1 ms 5212 KB Output is correct
3 Correct 7 ms 63068 KB Output is correct
4 Correct 6 ms 54884 KB Output is correct
5 Correct 7 ms 63064 KB Output is correct
6 Correct 19 ms 86872 KB Output is correct
7 Correct 19 ms 72536 KB Output is correct
8 Correct 14 ms 29532 KB Output is correct
9 Correct 7 ms 42844 KB Output is correct
10 Correct 6 ms 42844 KB Output is correct
11 Correct 6 ms 42844 KB Output is correct
12 Correct 22 ms 91484 KB Output is correct
13 Correct 23 ms 89816 KB Output is correct
14 Correct 19 ms 89436 KB Output is correct
15 Correct 20 ms 89432 KB Output is correct

Subtask #8
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7004 KB Output is correct
2 Correct 1 ms 5212 KB Output is correct
3 Correct 7 ms 63068 KB Output is correct
4 Correct 6 ms 54884 KB Output is correct
5 Correct 7 ms 63064 KB Output is correct
6 Correct 19 ms 86872 KB Output is correct
7 Correct 19 ms 72536 KB Output is correct
8 Correct 14 ms 29532 KB Output is correct
9 Correct 7 ms 42844 KB Output is correct
10 Correct 6 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 10 ms 42896 KB Output is correct
14 Correct 10 ms 42840 KB Output is correct
15 Correct 12 ms 43032 KB Output is correct
16 Correct 22 ms 91484 KB Output is correct
17 Correct 23 ms 89816 KB Output is correct
18 Correct 19 ms 89436 KB Output is correct
19 Correct 20 ms 89432 KB Output is correct
20 Correct 1558 ms 143568 KB Output is correct
21 Correct 1066 ms 146012 KB Output is correct
22 Correct 1504 ms 145800 KB Output is correct

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7004 KB Output is correct
2 Correct 1 ms 5212 KB Output is correct
3 Correct 7 ms 63068 KB Output is correct
4 Correct 6 ms 54884 KB Output is correct
5 Correct 7 ms 63064 KB Output is correct
6 Correct 19 ms 86872 KB Output is correct
7 Correct 19 ms 72536 KB Output is correct
8 Correct 14 ms 29532 KB Output is correct
9 Correct 226 ms 63060 KB Output is correct
10 Correct 33 ms 62300 KB Output is correct
11 Correct 19 ms 62300 KB Output is correct
12 Correct 19 ms 60248 KB Output is correct
13 Correct 827 ms 199540 KB Output is correct
14 Correct 896 ms 201628 KB Output is correct
15 Correct 840 ms 196180 KB Output is correct
16 Correct 814 ms 193616 KB Output is correct
17 Correct 7 ms 42844 KB Output is correct
18 Correct 6 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 10 ms 42896 KB Output is correct
22 Correct 10 ms 42840 KB Output is correct
23 Correct 12 ms 43032 KB Output is correct
24 Correct 22 ms 91484 KB Output is correct
25 Correct 23 ms 89816 KB Output is correct
26 Correct 19 ms 89436 KB Output is correct
27 Correct 20 ms 89432 KB Output is correct
28 Correct 1558 ms 143568 KB Output is correct
29 Correct 1066 ms 146012 KB Output is correct
30 Correct 1504 ms 145800 KB Output is correct
31 Execution timed out 2037 ms 232020 KB Time limit exceeded
32 Halted 0 ms 0 KB -