Submission #348561

#	Time	Username	Problem	Language	Result	Execution time	Memory
348561		2qbingxuan	Intergalactic ship (IZhO19_xorsum)	C++14	92 / 100	2100 ms	50128 KiB

xorsum

#pragma GCC optimize("Ofast")
#pragma GCC targat("avx2")
#pragma loop_opt(on)
#include <bits/stdc++.h>
#ifdef local
#define debug(args...) qqbx(#args, args)
template <typename ...T> void qqbx(const char *s, T ...args) {
    int cnt = sizeof...(T);
    ((std::cerr << "(" << s << ") = (") , ... , (std::cerr << args << (--cnt ? ", " : ")\n")));
}
#define TAK(args...) std::ostream &operator<<(std::ostream &O, args)
#define NIE(STL, BEG, END, OUT) template <typename ...T> TAK(std::STL<T...> v) \
    { int f=0; O << BEG; for(auto e: v) O << (f++ ? ", " : "") << OUT; return O << END; }
NIE(vector, "[", "]", e)
NIE(map, "{", "}", e.first << ',' << e.second)
template <typename T, size_t N> TAK(std::array<T,N> v) { return O << std::vector<T>(v.begin(), v.end()); }
#else
#define debug(...) ((void)0)
#define safe ((void)0)
#endif // local
#define pb emplace_back
#define all(v) begin(v),end(v)
#define int ll

using namespace std;
using ll = long long;
using ld = double;
const int N = 100002, MOD = 1000000007;
const ll INF = 1e18;
const ld PI = acos(-1);

struct Basis {
    vector<int> b;
    array<int,7> cnt;
    Basis() : b(), cnt{} {}
    Basis & operator+=(int x) {
        for(int y: b)
            x = min(x, x^y);
        if(x) {
            b.pb(x);
            for(int j = 0; j < 7; j++) if(x >> j & 1) ++cnt[j];
        }
        return *this;
    }
    vector<int> span() const {
        int n = b.size();
        vector<int> res(1<<n);
        for(int i = 0; i < n; i++) res[1<<i] = b[i];
        for(int i = 1; i < (1<<n); i++) res[i] = res[i&-i] ^ res[i-(i&-i)];
        return res;
    }
    int size() const { return b.size(); }
    int calc(int x) {
        // return sum(y^x for y in span());
        int res = 0;
        // for(int y: span())
        //     res += y ^ x;
        // return res;
        auto take = [](int n, int d) {
            if(n == 0) return d ? 0 : 1;
            return 1 << n-1;
        };
        int n = b.size();
        for(int j = 0; j < 7; j++)
            res += (1<<j) * (1<<(n-cnt[j])) * take(cnt[j], ~x>>j&1);
        return res;
    }
};

int cnt[1005][1005];
bitset<128> bA[1005][1005], bB[1005][1005], bC[1005][1005];
int query(int pre[][1005], int lx, int ly, int rx, int ry) {
    return pre[rx][ry] - (lx ? pre[lx-1][ry] : 0) - (ly ? pre[rx][ly-1] : 0) + (lx && ly ? pre[lx-1][ly-1] : 0);
}
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n, q;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    cin >> q;
    vector<int> pw(q+1);
    pw[0] = 1;
    for(int i = 1; i <= q; i++) pw[i] = pw[i-1] * 2LL % MOD;
    vector<tuple<int,int,int>> Qs(q);
    vector<tuple<int,int,int>> evt;
    for(auto &[l, r, x]: Qs) {
        cin >> l >> r >> x;
        --l, --r;
        evt.pb(l, 1, x);
        evt.pb(r+1, -1, x);
    }

    int ans = 0;
    sort(all(evt));
    map<int,int> mp;
    for(int i = 0, j = 0; i < n; i++) {
        while(j < q*2 && get<0>(evt[j]) <= i) {
            auto [_, v, x] = evt[j++];
            if(_ != i) continue;
            mp[x] += v;
            if(mp[x] == 0) mp.erase(x);
        }
        debug(mp);
        Basis b;
        // make basis
        for(auto [val, cnt]: mp)
            b += val;
        // enumerate basis
        int cnt = 1LL * pw[q - b.size()] * (i+1) * (n-i);
        for(int x: b.span()) {
            int ai = a[i] ^ x;
            ans = (ans + 1LL * ai * ai * cnt) % MOD;
            debug(ai, cnt);
        }
    }
    
    for(int b = 0; b < 128; b++) {
        for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) cnt[i][j] = 0;
        for(auto [l, r, x]: Qs) if(x == b) cnt[l][r] += 1;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(i) cnt[i][j] += cnt[i-1][j];
                if(j) cnt[i][j] += cnt[i][j-1];
                if(i && j) cnt[i][j] -= cnt[i-1][j-1];
            }
        }
        for(int i = 0; i < n; i++) {
            for(int j = i+1; j < n; j++) {
                if(query(cnt, 0, j, i, n-1))
                    bC[i][j][b] = true;
                if(query(cnt, 0, i, i, j-1))
                    bA[i][j][b] = true;
                if(query(cnt, i+1, j, j, n-1))
                    bB[i][j][b] = true;
            }
        }
    }

    auto calc = [&](int i, int j) {
        /*
        for(auto [l, r, x]: Qs) {
            if(l <= i && j <= r) {
                C += x;
            } else if(l <= i && r >= i && r < j) {
                A += x;
            } else if(l > i && l <= j && r >= j) {
                debug(l, r, i, j);
                B += x;
            }
        }
        */
        Basis A, B, C;
        for(int b = 0; b < 128; b++) {
            if(bA[i][j][b])
                A += b;
            if(bB[i][j][b])
                B += b;
            if(bC[i][j][b])
                C += b;
        }
        int res = 0;
        for(int x: C.span()) {
            int ai = a[i] ^ x, aj = a[j] ^ x;
            debug(ai, aj);
            res = (res + 1LL * A.calc(ai) * B.calc(aj)) % MOD;
        }
        debug(res);
        return 1LL * res * pw[q - (C.size() + A.size() + B.size())] % MOD;
    };

    for(int i = 0; i < n; i++) {
        for(int j = i+1; j < n; j++) {
            int cnt = 2 * (i+1) * (n-j);
            ans = (ans + 1LL * calc(i, j) * cnt) % MOD;
        }
    }

    cout << ans << '\n';
}

Compilation message (stderr)

xorsum.cpp:2: warning: ignoring #pragma GCC targat [-Wunknown-pragmas]
    2 | #pragma GCC targat("avx2")
      | 
xorsum.cpp:3: warning: ignoring #pragma loop_opt  [-Wunknown-pragmas]
    3 | #pragma loop_opt(on)
      | 
xorsum.cpp: In lambda function:
xorsum.cpp:61:26: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   61 |             return 1 << n-1;
      |                         ~^~
xorsum.cpp: In function 'int main()':
xorsum.cpp:87:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   87 |     for(auto &[l, r, x]: Qs) {
      |               ^
xorsum.cpp:99:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   99 |             auto [_, v, x] = evt[j++];
      |                  ^
xorsum.cpp:107:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  107 |         for(auto [val, cnt]: mp)
      |                  ^
xorsum.cpp:120:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  120 |         for(auto [l, r, x]: Qs) if(x == b) cnt[l][r] += 1;
      |                  ^

• 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: 0 / 8