oj.uz

Submission #348506

# Submission time Handle Problem Language Result Execution time Memory
348506 2021-01-15T05:30:07 Z 2qbingxuan Intergalactic ship (IZhO19_xorsum) C++14
56 / 100
 2000 ms 9824 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;
    }
};
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);
        }
    }

    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;
            }
        }
        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);
        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:79:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   79 |     for(auto &[l, r, x]: Qs) {
      |               ^
xorsum.cpp:91:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   91 |             auto [_, v, x] = evt[j++];
      |                  ^
xorsum.cpp:99:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   99 |         for(auto [val, cnt]: mp)
      |                  ^
xorsum.cpp: In lambda function:
xorsum.cpp:112:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  112 |         for(auto [l, r, x]: Qs) {
      |                  ^

Subtask #1
4.0 / 4.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2099 ms 9824 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 589 ms 364 KB Output is correct
2 Correct 478 ms 464 KB Output is correct
3 Correct 167 ms 492 KB Output is correct
4 Correct 107 ms 364 KB Output is correct

Subtask #5
8.0 / 8.0

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

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 29 ms 1072 KB Output is correct
5 Correct 29 ms 1072 KB Output is correct
6 Correct 28 ms 1072 KB Output is correct
7 Correct 29 ms 1072 KB Output is correct

Subtask #7
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 3 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 47 ms 364 KB Output is correct
13 Correct 52 ms 492 KB Output is correct
14 Correct 11 ms 364 KB Output is correct
15 Correct 33 ms 448 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 3 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 29 ms 1072 KB Output is correct
13 Correct 29 ms 1072 KB Output is correct
14 Correct 28 ms 1072 KB Output is correct
15 Correct 29 ms 1072 KB Output is correct
16 Correct 47 ms 364 KB Output is correct
17 Correct 52 ms 492 KB Output is correct
18 Correct 11 ms 364 KB Output is correct
19 Correct 33 ms 448 KB Output is correct
20 Execution timed out 2082 ms 9820 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 3 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Execution timed out 2099 ms 9824 KB Time limit exceeded
10 Halted 0 ms 0 KB -