oj.uz

Submission #992995

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

                                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 2 ms 6488 KB Output is correct
2 Correct 3 ms 8028 KB Output is correct
3 Correct 8 ms 39516 KB Output is correct
4 Correct 7 ms 39260 KB Output is correct
5 Correct 9 ms 37212 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 3 ms 8028 KB Output is correct
3 Correct 8 ms 39516 KB Output is correct
4 Correct 7 ms 39260 KB Output is correct
5 Correct 9 ms 37212 KB Output is correct
6 Correct 35 ms 85076 KB Output is correct
7 Correct 34 ms 82780 KB Output is correct
8 Correct 52 ms 82256 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 87388 KB Output is correct
2 Correct 71 ms 83776 KB Output is correct
3 Correct 34 ms 117260 KB Output is correct
4 Correct 40 ms 117276 KB Output is correct

Subtask #4
0 / 9.0

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

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 63376 KB Output is correct
2 Correct 14 ms 61276 KB Output is correct
3 Correct 17 ms 63320 KB Output is correct
4 Correct 39 ms 63580 KB Output is correct
5 Correct 30 ms 63580 KB Output is correct
6 Correct 32 ms 63580 KB Output is correct
7 Correct 30 ms 63580 KB Output is correct

Subtask #7
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 3 ms 8028 KB Output is correct
3 Correct 8 ms 39516 KB Output is correct
4 Correct 7 ms 39260 KB Output is correct
5 Correct 9 ms 37212 KB Output is correct
6 Correct 35 ms 85076 KB Output is correct
7 Correct 34 ms 82780 KB Output is correct
8 Correct 52 ms 82256 KB Output is correct
9 Correct 13 ms 63376 KB Output is correct
10 Correct 14 ms 61276 KB Output is correct
11 Correct 17 ms 63320 KB Output is correct
12 Correct 54 ms 123484 KB Output is correct
13 Correct 59 ms 123688 KB Output is correct
14 Correct 38 ms 121436 KB Output is correct
15 Correct 45 ms 123228 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 3 ms 8028 KB Output is correct
3 Correct 8 ms 39516 KB Output is correct
4 Correct 7 ms 39260 KB Output is correct
5 Correct 9 ms 37212 KB Output is correct
6 Correct 35 ms 85076 KB Output is correct
7 Correct 34 ms 82780 KB Output is correct
8 Correct 52 ms 82256 KB Output is correct
9 Correct 13 ms 63376 KB Output is correct
10 Correct 14 ms 61276 KB Output is correct
11 Correct 17 ms 63320 KB Output is correct
12 Correct 39 ms 63580 KB Output is correct
13 Correct 30 ms 63580 KB Output is correct
14 Correct 32 ms 63580 KB Output is correct
15 Correct 30 ms 63580 KB Output is correct
16 Correct 54 ms 123484 KB Output is correct
17 Correct 59 ms 123688 KB Output is correct
18 Correct 38 ms 121436 KB Output is correct
19 Correct 45 ms 123228 KB Output is correct
20 Runtime error 171 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 2 ms 6488 KB Output is correct
2 Correct 3 ms 8028 KB Output is correct
3 Correct 8 ms 39516 KB Output is correct
4 Correct 7 ms 39260 KB Output is correct
5 Correct 9 ms 37212 KB Output is correct
6 Correct 35 ms 85076 KB Output is correct
7 Correct 34 ms 82780 KB Output is correct
8 Correct 52 ms 82256 KB Output is correct
9 Correct 263 ms 87388 KB Output is correct
10 Correct 71 ms 83776 KB Output is correct
11 Correct 34 ms 117260 KB Output is correct
12 Correct 40 ms 117276 KB Output is correct
13 Runtime error 138 ms 262144 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -