oj.uz

Submission #992917

# Submission time Handle Problem Language Result Execution time Memory
992917 2024-06-05T08:18:59 Z danikoynov Intergalactic ship (IZhO19_xorsum) C++14
53 / 100
 2000 ms 16980 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];

vector < int > spot[(1 << maxbit) * 2][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].push_back(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 i = 1; i <= n; i ++)
    {
        for (int j = i; j <= n; j ++)
        {

            for (int bit_i = 0; bit_i < maxbit; bit_i ++)
            {
                for (int bit_j = 0; bit_j < maxbit; bit_j ++)
                {
                    int both = 0;
                    int ch_i = 0;
                    int ch_j = 0;
                    int neit = 0;

                    //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];
                    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 2 ms 8796 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 1 ms 8796 KB Output is correct
5 Correct 1 ms 8796 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 1 ms 8796 KB Output is correct
5 Correct 1 ms 8796 KB Output is correct
6 Correct 24 ms 8796 KB Output is correct
7 Correct 21 ms 8796 KB Output is correct
8 Correct 21 ms 8792 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1844 ms 13140 KB Output is correct
2 Correct 205 ms 9304 KB Output is correct
3 Correct 29 ms 8796 KB Output is correct
4 Correct 23 ms 8796 KB Output is correct

Subtask #4
0 / 9.0

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

Subtask #5
8.0 / 8.0

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

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8796 KB Output is correct
2 Correct 3 ms 8796 KB Output is correct
3 Correct 3 ms 8796 KB Output is correct
4 Correct 110 ms 9052 KB Output is correct
5 Correct 112 ms 9048 KB Output is correct
6 Correct 113 ms 9048 KB Output is correct
7 Correct 111 ms 9052 KB Output is correct

Subtask #7
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 1 ms 8796 KB Output is correct
5 Correct 1 ms 8796 KB Output is correct
6 Correct 24 ms 8796 KB Output is correct
7 Correct 21 ms 8796 KB Output is correct
8 Correct 21 ms 8792 KB Output is correct
9 Correct 3 ms 8796 KB Output is correct
10 Correct 3 ms 8796 KB Output is correct
11 Correct 3 ms 8796 KB Output is correct
12 Correct 112 ms 8796 KB Output is correct
13 Correct 113 ms 8880 KB Output is correct
14 Correct 36 ms 8792 KB Output is correct
15 Correct 45 ms 8796 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 1 ms 8796 KB Output is correct
5 Correct 1 ms 8796 KB Output is correct
6 Correct 24 ms 8796 KB Output is correct
7 Correct 21 ms 8796 KB Output is correct
8 Correct 21 ms 8792 KB Output is correct
9 Correct 3 ms 8796 KB Output is correct
10 Correct 3 ms 8796 KB Output is correct
11 Correct 3 ms 8796 KB Output is correct
12 Correct 110 ms 9052 KB Output is correct
13 Correct 112 ms 9048 KB Output is correct
14 Correct 113 ms 9048 KB Output is correct
15 Correct 111 ms 9052 KB Output is correct
16 Correct 112 ms 8796 KB Output is correct
17 Correct 113 ms 8880 KB Output is correct
18 Correct 36 ms 8792 KB Output is correct
19 Correct 45 ms 8796 KB Output is correct
20 Execution timed out 2068 ms 16980 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 1 ms 8796 KB Output is correct
5 Correct 1 ms 8796 KB Output is correct
6 Correct 24 ms 8796 KB Output is correct
7 Correct 21 ms 8796 KB Output is correct
8 Correct 21 ms 8792 KB Output is correct
9 Correct 1844 ms 13140 KB Output is correct
10 Correct 205 ms 9304 KB Output is correct
11 Correct 29 ms 8796 KB Output is correct
12 Correct 23 ms 8796 KB Output is correct
13 Execution timed out 2052 ms 8796 KB Time limit exceeded
14 Halted 0 ms 0 KB -