Submission #1103767

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103767		Mike_Vu	Intergalactic ship (IZhO19_xorsum)	C++14	100 / 100	562 ms	13048 KiB

xorsum

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double dou;
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define MASK(x) (1LL<<(x))
#define BITj(x, j) (((x)>>(j))&1)

template<typename T> bool maximize(T &x, const T &y) {
    if (x < y) {x = y; return 1;}
    return 0;
}
template<typename T> bool minimize(T &x, const T &y) {
    if (x > y) {x = y; return 1;}
    return 0;
}

namespace modulofunc{
    const int mod = 1e9+7;
    int add(int x, int y) {
        ll temp = x+y;
        if (temp >= mod) temp -= mod;
        return temp;
    }
    void ad(int &x, int y) {
        x = add(x, y);
    }
    int sub(int x, int y) {
        ll temp = x-y;
        if (temp < 0) temp += mod;
        return temp;
    }
    int mul(int x, int y) {
        return 1LL*x*y%mod;
    }
    int binpow(int x, int k) {
        int res = 1;
        while (k > 0) {
            if (k&1) res = mul(res, x);
            k >>= 1;
            x = mul(x, x);
        }
        return res;
    }
}
using namespace modulofunc;

const int maxn = 1005, lg = 7, maxq = 1e5+5;
int n, a[maxn], q;
int pw2[maxq];
int d[maxn][lg];
vector<int> inc[maxn][lg][lg]; //case 1
int d1[maxn][lg][lg]; //-=
int ans = 0;

void prep() {
    //2^i
    pw2[0] = 1;
    for (int i = 1; i < maxq; i++) {
        pw2[i] = mul(pw2[i-1], 2);
    }
}
int sumcomb(int n, bool j){
    if (n < 0) return 0;
    if (n == 0) return (j == 0);
    return pw2[n-1];
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    #define name "task"
//    if (fopen(name".inp", "r")) {
//        freopen(name".inp", "r", stdin);
//        freopen(name".out", "w", stdout);
//    }
    prep();
    //input
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    //tach bit from updates -> inc
    memset(d, 0, sizeof(d));
    cin >> q;
    for (int i = 1; i <= q; i++)
    {
        int l, r, x;
        cin >> l >> r >> x;
        for (int j = 0; j < lg; j++) {
            if (BITj(x, j)) {
//                cout << j << ' ';
                d[l][j]++;
                d[r+1][j]--;
                for (int j2 = 0; j2 < lg; j2++) {
                    if (BITj(x, j2)) {
                        inc[r][j][j2].pb(l);
                    }
                }
            }
        }
    }
//    cout << "\n";
    //precal d ->2, 3
    //cnt updates -> i
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < lg; j++) {
            d[i][j] += d[i-1][j];
        }
    }
//    for (int j = 0; j < lg; j++) {
//        for (int i = 1; i <= n; i++) {
//            cout << d[i][j] << ' ';
//        }
//        cout << "\n";
//    }
    //i: n-> 1
    memset(d1, 0, sizeof(d1));
    int allsum[lg][lg], cursum[lg][lg];
    memset(allsum, 0, sizeof(allsum));
    memset(cursum, 0, sizeof(cursum));
    for (int i = n; i; i--) {
        //cal i
        for (int x = 0; x < lg; x++) {
            int valbit = pw2[2*x];
            int valq = mul(pw2[q-d[i][x]], sumcomb(d[i][x], BITj(a[i],x)^1));
            int valseg = mul(i, n-i+1);
            ad(ans, mul(mul(valbit, valq), valseg));
//            int temp = mul(mul(valbit, valq), valseg);
//            if (temp > 0) {
//                cout << "case i: " << i << ' ' << x << ' ' << temp << "\n";
//            }
            //allsumi
            for (int y = 0; y < lg; y++) {
                for (int id : inc[i][x][y]) {
                    ++allsum[x][y];
                    d1[id][x][y]++;
                }
                allsum[x][y] -= d1[i+1][x][y];
                cursum[x][y] = allsum[x][y];
            }
        }
        //moi cap i, j: i -> 1
        for (int j = i; j; j--) {
            //cnt updates i and j
            //every bit x y
            for (int x = 0; x < lg; x++) {
                for (int y = 0; y < lg; y++) {
                    if (i == j && x <= y) {
                        cursum[x][y] -= d1[j][x][y];
                        continue;
                    }
                    int valbit, valq, valseg;
                    int case1 = cursum[x][y];
                    int case2 = d[j][y]-case1;
                    int case3 = d[i][x]-case1;
                    valbit = pw2[x+y+1];
                    bool biti = BITj(a[i], x), bitj = BITj(a[j], y);
                    valq = mul(mul(sumcomb(case3, biti^1), sumcomb(case2, bitj^1)), sumcomb(case1, 0)); //1 - 1
                    ad(valq, mul(mul(sumcomb(case3, biti), sumcomb(case2, bitj)), sumcomb(case1, 1))); //0 - 0
                    valq = mul(valq, pw2[q-case1-case2-case3]); //case4
                    valseg = mul(j, n-i+1);
                    ad(ans, mul(mul(valbit, valq), valseg));
//                    int temp = mul(mul(valbit, valq), valseg);
//                    if (max(x, y) < 2) {
//                        cout << "case bit: " <<  j << ' ' << i << ' ' << y << ' ' << x << "\n";
//                        cout << case1 << ' ' << case2 << ' ' << case3 << ' ' << valbit << ' ' << valq << ' ' << valseg << ' ' << temp << "\n";
////                        cout << bitj << ' ' << biti << ' ';
////                        cout << mul(mul(sumcomb(case3, biti^1), sumcomb(case2, bitj^1)), sumcomb(case1, 0)) << ' ';
////                        cout << mul(mul(sumcomb(case3, biti), sumcomb(case2, bitj)), sumcomb(case1, 1)) << ' ';
////                        cout << pw2[q-case1-case2-case3] << "\n";
//                    }
                    //reset
                    cursum[x][y] -= d1[j][x][y];
                }
            }
            //contribute to the sum
        }
    }
    cout << ans;
}
/*
2
3 2
1
2 2 3
64

2
2 1
2
2 2 3
1 2 2
56

2
1 3
1
1 2 2
*/

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