oj.uz

Submission #993001

# Submission time Handle Problem Language Result Execution time Memory
993001 2024-06-05T08:51:36 Z danikoynov Intergalactic ship (IZhO19_xorsum) C++14
83 / 100
 1600 ms 180052 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 = 510;

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[(1 << maxbit)][maxn][maxn];
int pref[(1 << maxbit)][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 mask = 0; mask < (1 << maxbit); mask ++)
    {
        for (int r = 1; r <= n; r ++)
        {
            for (int l = 1; l <= r; l ++)
            {
                pref[mask][l][r] = pref[mask][l - 1][r] + spot[mask][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));
            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;
                        l = pref[mask][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 3 ms 7772 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 6 ms 54876 KB Output is correct
4 Correct 6 ms 48896 KB Output is correct
5 Correct 6 ms 54876 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7772 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 6 ms 54876 KB Output is correct
4 Correct 6 ms 48896 KB Output is correct
5 Correct 6 ms 54876 KB Output is correct
6 Correct 25 ms 91736 KB Output is correct
7 Correct 25 ms 85428 KB Output is correct
8 Correct 21 ms 50876 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 72404 KB Output is correct
2 Correct 35 ms 71260 KB Output is correct
3 Correct 23 ms 71132 KB Output is correct
4 Correct 21 ms 71256 KB Output is correct

Subtask #4
0 / 9.0

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

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 41304 KB Output is correct
2 Correct 8 ms 41252 KB Output is correct
3 Correct 8 ms 41304 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 41304 KB Output is correct
2 Correct 8 ms 41252 KB Output is correct
3 Correct 8 ms 41304 KB Output is correct
4 Correct 10 ms 41308 KB Output is correct
5 Correct 11 ms 41232 KB Output is correct
6 Correct 11 ms 41396 KB Output is correct
7 Correct 11 ms 41308 KB Output is correct

Subtask #7
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7772 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 6 ms 54876 KB Output is correct
4 Correct 6 ms 48896 KB Output is correct
5 Correct 6 ms 54876 KB Output is correct
6 Correct 25 ms 91736 KB Output is correct
7 Correct 25 ms 85428 KB Output is correct
8 Correct 21 ms 50876 KB Output is correct
9 Correct 8 ms 41304 KB Output is correct
10 Correct 8 ms 41252 KB Output is correct
11 Correct 8 ms 41304 KB Output is correct
12 Correct 33 ms 93788 KB Output is correct
13 Correct 28 ms 93788 KB Output is correct
14 Correct 28 ms 93784 KB Output is correct
15 Correct 26 ms 93788 KB Output is correct

Subtask #8
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7772 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 6 ms 54876 KB Output is correct
4 Correct 6 ms 48896 KB Output is correct
5 Correct 6 ms 54876 KB Output is correct
6 Correct 25 ms 91736 KB Output is correct
7 Correct 25 ms 85428 KB Output is correct
8 Correct 21 ms 50876 KB Output is correct
9 Correct 8 ms 41304 KB Output is correct
10 Correct 8 ms 41252 KB Output is correct
11 Correct 8 ms 41304 KB Output is correct
12 Correct 10 ms 41308 KB Output is correct
13 Correct 11 ms 41232 KB Output is correct
14 Correct 11 ms 41396 KB Output is correct
15 Correct 11 ms 41308 KB Output is correct
16 Correct 33 ms 93788 KB Output is correct
17 Correct 28 ms 93788 KB Output is correct
18 Correct 28 ms 93784 KB Output is correct
19 Correct 26 ms 93788 KB Output is correct
20 Correct 1600 ms 179228 KB Output is correct
21 Correct 1111 ms 180048 KB Output is correct
22 Correct 1548 ms 180052 KB Output is correct

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7772 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 6 ms 54876 KB Output is correct
4 Correct 6 ms 48896 KB Output is correct
5 Correct 6 ms 54876 KB Output is correct
6 Correct 25 ms 91736 KB Output is correct
7 Correct 25 ms 85428 KB Output is correct
8 Correct 21 ms 50876 KB Output is correct
9 Correct 236 ms 72404 KB Output is correct
10 Correct 35 ms 71260 KB Output is correct
11 Correct 23 ms 71132 KB Output is correct
12 Correct 21 ms 71256 KB Output is correct
13 Incorrect 31 ms 100956 KB Output isn't correct
14 Halted 0 ms 0 KB -