oj.uz

답안 #993013

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
993013 2024-06-05T08:58:00 Z danikoynov Intergalactic ship (IZhO19_xorsum) C++14
92 / 100
 2000 ms 231968 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 + 100;

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[maxbit * maxbit][maxn][maxn];
int pref[maxbit * maxbit][maxn][maxn];
int ch[maxbit][maxn];
int mask_to_idx[(1 << maxbit)];
int idx_to_mask[maxbit * maxbit];

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 < q +  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);
    }

    int cnt = 0;
    for (int bit1 = 0; bit1 < maxbit; bit1 ++)
        for (int bit2 = bit1; bit2 < maxbit; bit2 ++)
        {
            int mask = ((1 << bit1) | (1 << bit2));
            cnt ++;
            mask_to_idx[mask] = cnt;
            idx_to_mask[cnt] = mask;
        }
    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_to_idx[mask]][task[i].l][task[i].r] ++;
                }
            }
    }

    for (int mask = 0; mask < (1 << maxbit); mask ++)
    {
        int idx = mask_to_idx[mask];
        for (int r = 1; r <= n; r ++)
        {
            for (int l = 1; l <= r; l ++)
            {
                pref[idx][l][r] = pref[idx][l - 1][r] + spot[idx][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)), idx = mask_to_idx[mask];
            for (int i = 1; i <= n; i ++)
            {
                for (int j = i; j <= n; j ++)
                    both += spot[idx][i][j];

                if (i > 1)
                {
                    for (int j = 1; j < i; j ++)
                        both -= spot[idx][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[idx][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 b = 0; b < 2; b ++)
                    {
                        int d_i = 0;
                        if ((val_i + d_i + b) % 2 == 0)
                            d_i = 1;
                        int d_j = 0;
                        if ((val_j + d_j + b) % 2 == 0)
                            d_j = 1;



                        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 + neit])) % mod;
                    res = (res * (ll)(i) * (ll)(n - j + 1)) % mod;
                    if (i != j)
                    {
                        res = (res * 2);
                        if (res >= mod)
                            res -= mod;
                    }
                    ans += res;
                    if (ans >= mod)
                        ans -= mod;


                }
                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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 7004 KB Output is correct
2 Correct 1 ms 5212 KB Output is correct
3 Correct 6 ms 63224 KB Output is correct
4 Correct 6 ms 54876 KB Output is correct
5 Correct 6 ms 63068 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 7004 KB Output is correct
2 Correct 1 ms 5212 KB Output is correct
3 Correct 6 ms 63224 KB Output is correct
4 Correct 6 ms 54876 KB Output is correct
5 Correct 6 ms 63068 KB Output is correct
6 Correct 20 ms 86876 KB Output is correct
7 Correct 15 ms 72540 KB Output is correct
8 Correct 12 ms 29532 KB Output is correct

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 215 ms 62924 KB Output is correct
2 Correct 32 ms 62296 KB Output is correct
3 Correct 13 ms 62552 KB Output is correct
4 Correct 14 ms 60392 KB Output is correct

Subtask #4
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 530 ms 202572 KB Output is correct
2 Correct 530 ms 203260 KB Output is correct
3 Correct 507 ms 202320 KB Output is correct
4 Correct 507 ms 201812 KB Output is correct

Subtask #5
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 42840 KB Output is correct
2 Correct 6 ms 42844 KB Output is correct
3 Correct 5 ms 42992 KB Output is correct

Subtask #6
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 42840 KB Output is correct
2 Correct 6 ms 42844 KB Output is correct
3 Correct 5 ms 42992 KB Output is correct
4 Correct 9 ms 42840 KB Output is correct
5 Correct 9 ms 43048 KB Output is correct
6 Correct 9 ms 42844 KB Output is correct
7 Correct 9 ms 42844 KB Output is correct

Subtask #7
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 7004 KB Output is correct
2 Correct 1 ms 5212 KB Output is correct
3 Correct 6 ms 63224 KB Output is correct
4 Correct 6 ms 54876 KB Output is correct
5 Correct 6 ms 63068 KB Output is correct
6 Correct 20 ms 86876 KB Output is correct
7 Correct 15 ms 72540 KB Output is correct
8 Correct 12 ms 29532 KB Output is correct
9 Correct 6 ms 42840 KB Output is correct
10 Correct 6 ms 42844 KB Output is correct
11 Correct 5 ms 42992 KB Output is correct
12 Correct 19 ms 97372 KB Output is correct
13 Correct 20 ms 97372 KB Output is correct
14 Correct 16 ms 97116 KB Output is correct
15 Correct 17 ms 97116 KB Output is correct

Subtask #8
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 7004 KB Output is correct
2 Correct 1 ms 5212 KB Output is correct
3 Correct 6 ms 63224 KB Output is correct
4 Correct 6 ms 54876 KB Output is correct
5 Correct 6 ms 63068 KB Output is correct
6 Correct 20 ms 86876 KB Output is correct
7 Correct 15 ms 72540 KB Output is correct
8 Correct 12 ms 29532 KB Output is correct
9 Correct 6 ms 42840 KB Output is correct
10 Correct 6 ms 42844 KB Output is correct
11 Correct 5 ms 42992 KB Output is correct
12 Correct 9 ms 42840 KB Output is correct
13 Correct 9 ms 43048 KB Output is correct
14 Correct 9 ms 42844 KB Output is correct
15 Correct 9 ms 42844 KB Output is correct
16 Correct 19 ms 97372 KB Output is correct
17 Correct 20 ms 97372 KB Output is correct
18 Correct 16 ms 97116 KB Output is correct
19 Correct 17 ms 97116 KB Output is correct
20 Correct 1464 ms 150344 KB Output is correct
21 Correct 962 ms 148568 KB Output is correct
22 Correct 1522 ms 150612 KB Output is correct

Subtask #9
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 7004 KB Output is correct
2 Correct 1 ms 5212 KB Output is correct
3 Correct 6 ms 63224 KB Output is correct
4 Correct 6 ms 54876 KB Output is correct
5 Correct 6 ms 63068 KB Output is correct
6 Correct 20 ms 86876 KB Output is correct
7 Correct 15 ms 72540 KB Output is correct
8 Correct 12 ms 29532 KB Output is correct
9 Correct 215 ms 62924 KB Output is correct
10 Correct 32 ms 62296 KB Output is correct
11 Correct 13 ms 62552 KB Output is correct
12 Correct 14 ms 60392 KB Output is correct
13 Correct 530 ms 202572 KB Output is correct
14 Correct 530 ms 203260 KB Output is correct
15 Correct 507 ms 202320 KB Output is correct
16 Correct 507 ms 201812 KB Output is correct
17 Correct 6 ms 42840 KB Output is correct
18 Correct 6 ms 42844 KB Output is correct
19 Correct 5 ms 42992 KB Output is correct
20 Correct 9 ms 42840 KB Output is correct
21 Correct 9 ms 43048 KB Output is correct
22 Correct 9 ms 42844 KB Output is correct
23 Correct 9 ms 42844 KB Output is correct
24 Correct 19 ms 97372 KB Output is correct
25 Correct 20 ms 97372 KB Output is correct
26 Correct 16 ms 97116 KB Output is correct
27 Correct 17 ms 97116 KB Output is correct
28 Correct 1464 ms 150344 KB Output is correct
29 Correct 962 ms 148568 KB Output is correct
30 Correct 1522 ms 150612 KB Output is correct
31 Execution timed out 2088 ms 231968 KB Time limit exceeded
32 Halted 0 ms 0 KB -