oj.uz

Submission #992997

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

                                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 4 ms 6492 KB Output is correct
2 Correct 3 ms 8028 KB Output is correct
3 Correct 13 ms 72040 KB Output is correct
4 Correct 9 ms 61788 KB Output is correct
5 Correct 10 ms 69888 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6492 KB Output is correct
2 Correct 3 ms 8028 KB Output is correct
3 Correct 13 ms 72040 KB Output is correct
4 Correct 9 ms 61788 KB Output is correct
5 Correct 10 ms 69888 KB Output is correct
6 Correct 38 ms 118828 KB Output is correct
7 Correct 40 ms 119720 KB Output is correct
8 Correct 34 ms 98908 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 116916 KB Output is correct
2 Correct 60 ms 117332 KB Output is correct
3 Correct 34 ms 115540 KB Output is correct
4 Correct 39 ms 119132 KB Output is correct

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 134 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 15 ms 63320 KB Output is correct
2 Correct 14 ms 61452 KB Output is correct
3 Correct 13 ms 61276 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 63320 KB Output is correct
2 Correct 14 ms 61452 KB Output is correct
3 Correct 13 ms 61276 KB Output is correct
4 Correct 21 ms 63580 KB Output is correct
5 Correct 16 ms 63604 KB Output is correct
6 Correct 15 ms 61532 KB Output is correct
7 Correct 16 ms 59484 KB Output is correct

Subtask #7
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6492 KB Output is correct
2 Correct 3 ms 8028 KB Output is correct
3 Correct 13 ms 72040 KB Output is correct
4 Correct 9 ms 61788 KB Output is correct
5 Correct 10 ms 69888 KB Output is correct
6 Correct 38 ms 118828 KB Output is correct
7 Correct 40 ms 119720 KB Output is correct
8 Correct 34 ms 98908 KB Output is correct
9 Correct 15 ms 63320 KB Output is correct
10 Correct 14 ms 61452 KB Output is correct
11 Correct 13 ms 61276 KB Output is correct
12 Correct 43 ms 129124 KB Output is correct
13 Correct 37 ms 98708 KB Output is correct
14 Correct 37 ms 132712 KB Output is correct
15 Correct 43 ms 134120 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6492 KB Output is correct
2 Correct 3 ms 8028 KB Output is correct
3 Correct 13 ms 72040 KB Output is correct
4 Correct 9 ms 61788 KB Output is correct
5 Correct 10 ms 69888 KB Output is correct
6 Correct 38 ms 118828 KB Output is correct
7 Correct 40 ms 119720 KB Output is correct
8 Correct 34 ms 98908 KB Output is correct
9 Correct 15 ms 63320 KB Output is correct
10 Correct 14 ms 61452 KB Output is correct
11 Correct 13 ms 61276 KB Output is correct
12 Correct 21 ms 63580 KB Output is correct
13 Correct 16 ms 63604 KB Output is correct
14 Correct 15 ms 61532 KB Output is correct
15 Correct 16 ms 59484 KB Output is correct
16 Correct 43 ms 129124 KB Output is correct
17 Correct 37 ms 98708 KB Output is correct
18 Correct 37 ms 132712 KB Output is correct
19 Correct 43 ms 134120 KB Output is correct
20 Runtime error 150 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 4 ms 6492 KB Output is correct
2 Correct 3 ms 8028 KB Output is correct
3 Correct 13 ms 72040 KB Output is correct
4 Correct 9 ms 61788 KB Output is correct
5 Correct 10 ms 69888 KB Output is correct
6 Correct 38 ms 118828 KB Output is correct
7 Correct 40 ms 119720 KB Output is correct
8 Correct 34 ms 98908 KB Output is correct
9 Correct 246 ms 116916 KB Output is correct
10 Correct 60 ms 117332 KB Output is correct
11 Correct 34 ms 115540 KB Output is correct
12 Correct 39 ms 119132 KB Output is correct
13 Runtime error 134 ms 262144 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -