oj.uz

Submission #992993

# Submission time Handle Problem Language Result Execution time Memory
992993 2024-06-05T08:48:14 Z danikoynov Intergalactic ship (IZhO19_xorsum) C++14
53 / 100
 596 ms 262144 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[(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];
                                }
                                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;
                    }

                }
                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 6492 KB Output is correct
2 Correct 3 ms 7912 KB Output is correct
3 Correct 9 ms 35420 KB Output is correct
4 Correct 6 ms 33116 KB Output is correct
5 Correct 8 ms 35256 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6492 KB Output is correct
2 Correct 3 ms 7912 KB Output is correct
3 Correct 9 ms 35420 KB Output is correct
4 Correct 6 ms 33116 KB Output is correct
5 Correct 8 ms 35256 KB Output is correct
6 Correct 49 ms 122452 KB Output is correct
7 Correct 38 ms 86876 KB Output is correct
8 Correct 36 ms 85840 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 596 ms 96768 KB Output is correct
2 Correct 92 ms 125012 KB Output is correct
3 Correct 39 ms 90996 KB Output is correct
4 Correct 39 ms 124496 KB Output is correct

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 147 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 63500 KB Output is correct
2 Correct 15 ms 49412 KB Output is correct
3 Correct 11 ms 47448 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 63500 KB Output is correct
2 Correct 15 ms 49412 KB Output is correct
3 Correct 11 ms 47448 KB Output is correct
4 Correct 71 ms 47448 KB Output is correct
5 Correct 75 ms 49500 KB Output is correct
6 Correct 71 ms 49496 KB Output is correct
7 Correct 91 ms 51548 KB Output is correct

Subtask #7
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6492 KB Output is correct
2 Correct 3 ms 7912 KB Output is correct
3 Correct 9 ms 35420 KB Output is correct
4 Correct 6 ms 33116 KB Output is correct
5 Correct 8 ms 35256 KB Output is correct
6 Correct 49 ms 122452 KB Output is correct
7 Correct 38 ms 86876 KB Output is correct
8 Correct 36 ms 85840 KB Output is correct
9 Correct 13 ms 63500 KB Output is correct
10 Correct 15 ms 49412 KB Output is correct
11 Correct 11 ms 47448 KB Output is correct
12 Correct 105 ms 87896 KB Output is correct
13 Correct 85 ms 89684 KB Output is correct
14 Correct 49 ms 123484 KB Output is correct
15 Correct 52 ms 85336 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6492 KB Output is correct
2 Correct 3 ms 7912 KB Output is correct
3 Correct 9 ms 35420 KB Output is correct
4 Correct 6 ms 33116 KB Output is correct
5 Correct 8 ms 35256 KB Output is correct
6 Correct 49 ms 122452 KB Output is correct
7 Correct 38 ms 86876 KB Output is correct
8 Correct 36 ms 85840 KB Output is correct
9 Correct 13 ms 63500 KB Output is correct
10 Correct 15 ms 49412 KB Output is correct
11 Correct 11 ms 47448 KB Output is correct
12 Correct 71 ms 47448 KB Output is correct
13 Correct 75 ms 49500 KB Output is correct
14 Correct 71 ms 49496 KB Output is correct
15 Correct 91 ms 51548 KB Output is correct
16 Correct 105 ms 87896 KB Output is correct
17 Correct 85 ms 89684 KB Output is correct
18 Correct 49 ms 123484 KB Output is correct
19 Correct 52 ms 85336 KB Output is correct
20 Runtime error 153 ms 262144 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6492 KB Output is correct
2 Correct 3 ms 7912 KB Output is correct
3 Correct 9 ms 35420 KB Output is correct
4 Correct 6 ms 33116 KB Output is correct
5 Correct 8 ms 35256 KB Output is correct
6 Correct 49 ms 122452 KB Output is correct
7 Correct 38 ms 86876 KB Output is correct
8 Correct 36 ms 85840 KB Output is correct
9 Correct 596 ms 96768 KB Output is correct
10 Correct 92 ms 125012 KB Output is correct
11 Correct 39 ms 90996 KB Output is correct
12 Correct 39 ms 124496 KB Output is correct
13 Runtime error 147 ms 262144 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -