oj.uz

Submission #1103767

# Submission time Handle Problem Language Result Execution time Memory
1103767 2024-10-21T16:09:46 Z Mike_Vu Intergalactic ship (IZhO19_xorsum) C++14
100 / 100
 562 ms 13048 KB 
#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.0 / 4.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 6736 KB Output is correct
2 Correct 11 ms 2812 KB Output is correct
3 Correct 7 ms 2128 KB Output is correct
4 Correct 8 ms 2020 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 2384 KB Output is correct
2 Correct 451 ms 2396 KB Output is correct
3 Correct 450 ms 2268 KB Output is correct
4 Correct 423 ms 2128 KB Output is correct

Subtask #5
8.0 / 8.0

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

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2128 KB Output is correct
2 Correct 3 ms 2128 KB Output is correct
3 Correct 3 ms 2128 KB Output is correct
4 Correct 4 ms 2384 KB Output is correct
5 Correct 4 ms 2448 KB Output is correct
6 Correct 4 ms 2384 KB Output is correct
7 Correct 4 ms 2384 KB Output is correct

Subtask #7
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2128 KB Output is correct
2 Correct 2 ms 2128 KB Output is correct
3 Correct 2 ms 2128 KB Output is correct
4 Correct 3 ms 2128 KB Output is correct
5 Correct 3 ms 2128 KB Output is correct
6 Correct 8 ms 2128 KB Output is correct
7 Correct 7 ms 2128 KB Output is correct
8 Correct 7 ms 2128 KB Output is correct
9 Correct 3 ms 2128 KB Output is correct
10 Correct 3 ms 2128 KB Output is correct
11 Correct 3 ms 2128 KB Output is correct
12 Correct 7 ms 2128 KB Output is correct
13 Correct 7 ms 2324 KB Output is correct
14 Correct 7 ms 2296 KB Output is correct
15 Correct 7 ms 2040 KB Output is correct

Subtask #8
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2128 KB Output is correct
2 Correct 2 ms 2128 KB Output is correct
3 Correct 2 ms 2128 KB Output is correct
4 Correct 3 ms 2128 KB Output is correct
5 Correct 3 ms 2128 KB Output is correct
6 Correct 8 ms 2128 KB Output is correct
7 Correct 7 ms 2128 KB Output is correct
8 Correct 7 ms 2128 KB Output is correct
9 Correct 3 ms 2128 KB Output is correct
10 Correct 3 ms 2128 KB Output is correct
11 Correct 3 ms 2128 KB Output is correct
12 Correct 4 ms 2384 KB Output is correct
13 Correct 4 ms 2448 KB Output is correct
14 Correct 4 ms 2384 KB Output is correct
15 Correct 4 ms 2384 KB Output is correct
16 Correct 7 ms 2128 KB Output is correct
17 Correct 7 ms 2324 KB Output is correct
18 Correct 7 ms 2296 KB Output is correct
19 Correct 7 ms 2040 KB Output is correct
20 Correct 164 ms 12368 KB Output is correct
21 Correct 179 ms 11592 KB Output is correct
22 Correct 139 ms 4176 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2128 KB Output is correct
2 Correct 2 ms 2128 KB Output is correct
3 Correct 2 ms 2128 KB Output is correct
4 Correct 3 ms 2128 KB Output is correct
5 Correct 3 ms 2128 KB Output is correct
6 Correct 8 ms 2128 KB Output is correct
7 Correct 7 ms 2128 KB Output is correct
8 Correct 7 ms 2128 KB Output is correct
9 Correct 28 ms 6736 KB Output is correct
10 Correct 11 ms 2812 KB Output is correct
11 Correct 7 ms 2128 KB Output is correct
12 Correct 8 ms 2020 KB Output is correct
13 Correct 474 ms 2384 KB Output is correct
14 Correct 451 ms 2396 KB Output is correct
15 Correct 450 ms 2268 KB Output is correct
16 Correct 423 ms 2128 KB Output is correct
17 Correct 3 ms 2128 KB Output is correct
18 Correct 3 ms 2128 KB Output is correct
19 Correct 3 ms 2128 KB Output is correct
20 Correct 4 ms 2384 KB Output is correct
21 Correct 4 ms 2448 KB Output is correct
22 Correct 4 ms 2384 KB Output is correct
23 Correct 4 ms 2384 KB Output is correct
24 Correct 7 ms 2128 KB Output is correct
25 Correct 7 ms 2324 KB Output is correct
26 Correct 7 ms 2296 KB Output is correct
27 Correct 7 ms 2040 KB Output is correct
28 Correct 164 ms 12368 KB Output is correct
29 Correct 179 ms 11592 KB Output is correct
30 Correct 139 ms 4176 KB Output is correct
31 Correct 562 ms 13048 KB Output is correct
32 Correct 500 ms 11848 KB Output is correct
33 Correct 495 ms 3932 KB Output is correct
34 Correct 523 ms 9672 KB Output is correct
35 Correct 523 ms 9840 KB Output is correct
36 Correct 520 ms 9800 KB Output is correct