oj.uz

Submission #348520

# Submission time Handle Problem Language Result Execution time Memory
348520 2021-01-15T06:01:23 Z 2qbingxuan Intergalactic ship (IZhO19_xorsum) C++14
53 / 100
 285 ms 262148 KB 
#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;
    }
    size_t 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[128][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);
        cnt[x][l][r] += 1;
    }

    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++) {
                if(i) cnt[b][i][j] += cnt[b][i-1][j];
                if(j) cnt[b][i][j] += cnt[b][i][j-1];
                if(i && j) cnt[b][i][j] -= cnt[b][i-1][j-1];
            }
        }
    }

    auto calc = [&](int i, int j) {
        Basis A, B, C;
        /*
        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;
            }
        }
        */
        for(int b = 0; b < 128; b++) {
            if(query(cnt[b], 0, j, i, n-1))
                C += b;
            if(query(cnt[b], 0, i, i, j-1))
                A += b;
            if(query(cnt[b], i+1, j, j, n-1))
                B += b;
        }
        debug(A.b, B.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);
        debug(pw.size(), q , C.size() , A.size() , B.size());
        return 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

xorsum.cpp: In lambda function:
xorsum.cpp:58:26: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   58 |             return 1 << n-1;
      |                         ~^~
xorsum.cpp: In function 'int main()':
xorsum.cpp:83:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   83 |     for(auto &[l, r, x]: Qs) {
      |               ^
xorsum.cpp:96:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   96 |             auto [_, v, x] = evt[j++];
      |                  ^
xorsum.cpp:104:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  104 |         for(auto [val, cnt]: mp)
      |                  ^

Subtask #1
4.0 / 4.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1900 KB Output is correct
2 Correct 3 ms 3436 KB Output is correct
3 Correct 4 ms 6124 KB Output is correct
4 Correct 4 ms 6124 KB Output is correct
5 Correct 5 ms 6124 KB Output is correct
6 Correct 63 ms 62188 KB Output is correct
7 Correct 59 ms 62188 KB Output is correct
8 Correct 61 ms 62188 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 70100 KB Output is correct
2 Correct 72 ms 63076 KB Output is correct
3 Correct 63 ms 62188 KB Output is correct
4 Correct 63 ms 62208 KB Output is correct

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 285 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
8.0 / 8.0

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

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 17152 KB Output is correct
2 Correct 14 ms 17132 KB Output is correct
3 Correct 14 ms 17132 KB Output is correct
4 Correct 17 ms 17644 KB Output is correct
5 Correct 17 ms 17644 KB Output is correct
6 Correct 19 ms 17644 KB Output is correct
7 Correct 17 ms 17664 KB Output is correct

Subtask #7
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1900 KB Output is correct
2 Correct 3 ms 3436 KB Output is correct
3 Correct 4 ms 6124 KB Output is correct
4 Correct 4 ms 6124 KB Output is correct
5 Correct 5 ms 6124 KB Output is correct
6 Correct 63 ms 62188 KB Output is correct
7 Correct 59 ms 62188 KB Output is correct
8 Correct 61 ms 62188 KB Output is correct
9 Correct 14 ms 17152 KB Output is correct
10 Correct 14 ms 17132 KB Output is correct
11 Correct 14 ms 17132 KB Output is correct
12 Correct 98 ms 62188 KB Output is correct
13 Correct 98 ms 62188 KB Output is correct
14 Correct 64 ms 62188 KB Output is correct
15 Correct 79 ms 62316 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1900 KB Output is correct
2 Correct 3 ms 3436 KB Output is correct
3 Correct 4 ms 6124 KB Output is correct
4 Correct 4 ms 6124 KB Output is correct
5 Correct 5 ms 6124 KB Output is correct
6 Correct 63 ms 62188 KB Output is correct
7 Correct 59 ms 62188 KB Output is correct
8 Correct 61 ms 62188 KB Output is correct
9 Correct 14 ms 17152 KB Output is correct
10 Correct 14 ms 17132 KB Output is correct
11 Correct 14 ms 17132 KB Output is correct
12 Correct 17 ms 17644 KB Output is correct
13 Correct 17 ms 17644 KB Output is correct
14 Correct 19 ms 17644 KB Output is correct
15 Correct 17 ms 17664 KB Output is correct
16 Correct 98 ms 62188 KB Output is correct
17 Correct 98 ms 62188 KB Output is correct
18 Correct 64 ms 62188 KB Output is correct
19 Correct 79 ms 62316 KB Output is correct
20 Runtime error 234 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1900 KB Output is correct
2 Correct 3 ms 3436 KB Output is correct
3 Correct 4 ms 6124 KB Output is correct
4 Correct 4 ms 6124 KB Output is correct
5 Correct 5 ms 6124 KB Output is correct
6 Correct 63 ms 62188 KB Output is correct
7 Correct 59 ms 62188 KB Output is correct
8 Correct 61 ms 62188 KB Output is correct
9 Correct 124 ms 70100 KB Output is correct
10 Correct 72 ms 63076 KB Output is correct
11 Correct 63 ms 62188 KB Output is correct
12 Correct 63 ms 62208 KB Output is correct
13 Runtime error 285 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -