Submission #1138965

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138965		AHOKA	Intergalactic ship (IZhO19_xorsum)	C++20	0 / 100	26 ms	5556 KiB

xorsum

#pragma GCC optimize("O3") 

#include <bits/stdc++.h>

using namespace std;
 
#define threesum cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false)
#define all(a) a.begin(), a.end()
#define F first
#define S second
#define int long long
#define double long double
#define pii pair<int, int>
#define ppp pair<int, pii>
#define dout cout << fixed << setprecision(15)
#define mid ((l + r) / 2)
#define lc (2 * id)
#define rc (lc + 1)

const int maxn = 3e5 + 10, maxm = 1e2 + 10, oo = 1e18 + 10, lg = 8, sq = 350, mod = 1e9 + 7;

int n, m, a[maxm], dp[maxm][maxm][4], p[maxn], ans;

vector<ppp> q;

void build(int b1, int b2){
    for (int i = 1; i <= n;i++)
        for (int j = 1; j <= n;j++)
            for (int k = 0; k < 4;k++)
                dp[i][j][k] = 0;

    for(auto [x, pr] : q){
        auto [l, r] = pr;
        dp[l][r][2 * ((x >> b1) & 1ll) + ((x >> b2) & 1ll)]++;
    }

    for (int len = n; len;len--)
        for (int l = 1, r = len; r <= n; l++, r++)
            for (int k = 0; k < 4;k++)
                dp[l][r][k] += dp[l - 1][r][k] + dp[l][r + 1][k] - dp[l - 1][r + 1][k];
}

signed main()
{
	threesum;
    cin >> n;
    for (int i = 1; i <= n;i++)
        cin >> a[i];

    cin >> m;
    for (int i = 1; i <= m;i++){
        int l, r, x;
        cin >> l >> r >> x;
        q.push_back({x, {l, r}});
    }

    p[0] = 1;
    for (int i = 1; i < maxn;i++)
        p[i] = (2 * p[i - 1]) % mod;

    for (int b1 = 0; b1 < lg;b1++)
        for (int b2 = 0; b2 < lg;b2++){
            build(b1, b2);

            for (int i = 1; i <= n;i++)
                for (int j = i; j <= n;j++){
                    int cnt[2][2];

                    cnt[1][1] = dp[i][j][3];
                    cnt[0][1] = dp[j][j][1] + dp[j][j][3] - cnt[1][1];
                    cnt[1][0] = dp[i][i][2] + dp[i][i][3] - cnt[1][1];

                    int c = 0;

                    if(cnt[0][1]){
                        if(cnt[1][0])
                            c = p[cnt[0][1] - 1 + cnt[1][0] - 1];
                        else if (cnt[1][1])
                            c = p[cnt[0][1] - 1 + cnt[1][1] - 1];
                        else if(a[i] & (1ll << b1)) 
                            c = p[cnt[0][1] - 1];
                    }
                    else if(cnt[1][0]){
                        if(cnt[1][1])
                            c = p[cnt[1][0] - 1 + cnt[1][1] - 1];
                        else if(a[j] & (1ll << b2)) 
                            c = p[cnt[1][0] - 1];
                    }
                    else if(((a[i] >> b1) & 1ll) == ((a[j] >> b2) & 1ll)){
                        if(cnt[1][1])
                            c = p[cnt[1][1] - 1];
                        else if(a[i] & (1ll << b1))
                            c = 1;
                    }

                    (c *= p[m - cnt[1][1] - cnt[0][1] - cnt[1][0]]) %= mod;
                    (c *= i * (n - j + 1)) %= mod;
                    (c *= (2 - (i == j))) %= mod;

                    (ans += (c * p[b1 + b2]) % mod) %= mod;
                }
        }

    cout << ans;
}
/*
3
1 2 3
2
1 2 1
2 3 2
*/

• Subtask 1: 0 / 4
• Subtask 2: 0 / 5
• Subtask 3: 0 / 6
• Subtask 4: 0 / 9
• Subtask 5: 0 / 8
• Subtask 6: 0 / 11
• Subtask 7: 0 / 19
• Subtask 8: 0 / 30
• Subtask 9: 0 / 8