oj.uz

Submission #992931

# Submission time Handle Problem Language Result Execution time Memory
992931 2024-06-05T08:23:26 Z danikoynov Intergalactic ship (IZhO19_xorsum) C++14
53 / 100
 2000 ms 81236 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];
bitset < 310 > bt[maxbit][maxn];

int spot[(1 << maxbit) * 2][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 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);
                bt[bit][i][j] = 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 ++)
        {

            for (int i = 1; i <= n; i ++)
            {
                for (int j = i; j <= n; j ++)
                {

                    int both = 0;
                    int ch_i = 0;
                    int ch_j = 0;
                    int neit = 0;
                    int mask =((1 << bit_i) | (1 << bit_j));
                    //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];
                    for (int ii = 1; ii <= i; ii ++)
                        for (int jj = j; jj <= n; jj ++)
                        both += spot[mask][ii][jj];
                    ///both = get_both(((1 << bit_i) | (1 << bit_j)), i, j);
                    //both = (bt[bit_i][i] & bt[bit_j][j]).count();
                    //assert(both <= get_both(((1 << bit_i) | (1 << bit_j)), i, j));
                    ch_i -= both;
                    ch_j -= both;
                    neit = q - both - ch_i - ch_j;
                    /**for (int t = 1; t <= q; t ++)
                    {
                        bool af_i = is_affected(i, bit_i, t), af_j = is_affected(j, bit_j, t);
                        if (af_i == false && af_j == false)
                            neit ++;
                        else if (af_i == true && af_j == false)
                            ch_i ++;
                        else if (af_i == false && af_j == true)
                            ch_j ++;
                        else if (af_i == true && af_j == true)
                            both ++;
                    }*/

                    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;
                                for (int l = d_i; l <= ch_i;  l += 2)
                                {
                                    way_i += comb(ch_i, l);
                                    if (way_i >= mod)
                                        way_i -= mod;
                                }
                                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;
                    }

                }
            }
        }
    }

    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 4700 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 6 ms 59836 KB Output is correct
4 Correct 6 ms 51800 KB Output is correct
5 Correct 6 ms 57948 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 6 ms 59836 KB Output is correct
4 Correct 6 ms 51800 KB Output is correct
5 Correct 6 ms 57948 KB Output is correct
6 Correct 106 ms 57948 KB Output is correct
7 Correct 112 ms 47696 KB Output is correct
8 Correct 100 ms 4688 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 991 ms 43348 KB Output is correct
2 Correct 186 ms 41632 KB Output is correct
3 Correct 111 ms 41556 KB Output is correct
4 Correct 111 ms 41784 KB Output is correct

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2020 ms 68952 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33368 KB Output is correct
2 Correct 7 ms 33372 KB Output is correct
3 Correct 7 ms 33372 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33368 KB Output is correct
2 Correct 7 ms 33372 KB Output is correct
3 Correct 7 ms 33372 KB Output is correct
4 Correct 106 ms 35424 KB Output is correct
5 Correct 106 ms 35420 KB Output is correct
6 Correct 109 ms 35416 KB Output is correct
7 Correct 106 ms 35428 KB Output is correct

Subtask #7
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 6 ms 59836 KB Output is correct
4 Correct 6 ms 51800 KB Output is correct
5 Correct 6 ms 57948 KB Output is correct
6 Correct 106 ms 57948 KB Output is correct
7 Correct 112 ms 47696 KB Output is correct
8 Correct 100 ms 4688 KB Output is correct
9 Correct 6 ms 33368 KB Output is correct
10 Correct 7 ms 33372 KB Output is correct
11 Correct 7 ms 33372 KB Output is correct
12 Correct 183 ms 62044 KB Output is correct
13 Correct 196 ms 60500 KB Output is correct
14 Correct 113 ms 60252 KB Output is correct
15 Correct 125 ms 59996 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 6 ms 59836 KB Output is correct
4 Correct 6 ms 51800 KB Output is correct
5 Correct 6 ms 57948 KB Output is correct
6 Correct 106 ms 57948 KB Output is correct
7 Correct 112 ms 47696 KB Output is correct
8 Correct 100 ms 4688 KB Output is correct
9 Correct 6 ms 33368 KB Output is correct
10 Correct 7 ms 33372 KB Output is correct
11 Correct 7 ms 33372 KB Output is correct
12 Correct 106 ms 35424 KB Output is correct
13 Correct 106 ms 35420 KB Output is correct
14 Correct 109 ms 35416 KB Output is correct
15 Correct 106 ms 35428 KB Output is correct
16 Correct 183 ms 62044 KB Output is correct
17 Correct 196 ms 60500 KB Output is correct
18 Correct 113 ms 60252 KB Output is correct
19 Correct 125 ms 59996 KB Output is correct
20 Execution timed out 2040 ms 81236 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 6 ms 59836 KB Output is correct
4 Correct 6 ms 51800 KB Output is correct
5 Correct 6 ms 57948 KB Output is correct
6 Correct 106 ms 57948 KB Output is correct
7 Correct 112 ms 47696 KB Output is correct
8 Correct 100 ms 4688 KB Output is correct
9 Correct 991 ms 43348 KB Output is correct
10 Correct 186 ms 41632 KB Output is correct
11 Correct 111 ms 41556 KB Output is correct
12 Correct 111 ms 41784 KB Output is correct
13 Execution timed out 2020 ms 68952 KB Time limit exceeded
14 Halted 0 ms 0 KB -