Submission #899111

#	Time	Username	Problem	Language	Result	Execution time	Memory
899111		d4xn	Intergalactic ship (IZhO19_xorsum)	C++17	17 / 100	2066 ms	11612 KiB

xorsum

#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math,inline")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,lzcnt,mmx,abm,avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define tp3 tuple<int, int, int>
 
const int N = 1e6+6, mod = 1e9+7;
 
int n, q, a[N], b[N], f[N];
tp3 queries[N];
 
/*
dp[i][j] de cuantas formas puedo ir al array i con las j primeras queries
*/
 
signed main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);
 
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  cin >> q;
  for (int i = 0; i < q; i++) {
    int l, r, x;
    cin >> l >> r >> x;
    l--; r--;
    queries[i] = make_tuple(l, r, x);
  }
 
  int ans = 0;
  for (int mask = 0; mask < (1 << q); mask++) {
    for (int i = 0; i < n; i++) {
      f[i] = 0;
      b[i] = a[i];
    }
 
    for (int i = 0; i < q; i++) {
      if ((mask >> i) & 1) {
        int l = get<0>(queries[i]);
        int r = get<1>(queries[i]);
        int x = get<2>(queries[i]);
        f[l] ^= x;
        f[r+1] ^= x;
      }
    }
 
    for (int i = 0; i < n; i++) {
      if (i) f[i] ^= f[i-1];
      b[i] ^= f[i];
    }
 
    for (int i = 0; i < n; i++) {
      int sum = 0;
      for (int j = i; j < n; j++) {
        sum += b[j];
        
        ans += sum*sum % mod;
        ans %= mod;
      }
    }
  }
 
  cout << ans << "\n";
}

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