oj.uz

Submission #898313

# Submission time Handle Problem Language Result Execution time Memory
898313 2024-01-04T13:29:41 Z vjudge1 Intergalactic ship (IZhO19_xorsum) C++17
17 / 100
 2000 ms 11356 KB 
#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.0 / 4.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 11356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

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

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1582 ms 6588 KB Output is correct
2 Correct 1584 ms 6592 KB Output is correct
3 Correct 1577 ms 6588 KB Output is correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1582 ms 6588 KB Output is correct
2 Correct 1584 ms 6592 KB Output is correct
3 Correct 1577 ms 6588 KB Output is correct
4 Incorrect 2 ms 6744 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 17 ms 6492 KB Output is correct
7 Correct 17 ms 6620 KB Output is correct
8 Correct 17 ms 6488 KB Output is correct
9 Correct 1582 ms 6588 KB Output is correct
10 Correct 1584 ms 6592 KB Output is correct
11 Correct 1577 ms 6588 KB Output is correct
12 Incorrect 67 ms 6740 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 17 ms 6492 KB Output is correct
7 Correct 17 ms 6620 KB Output is correct
8 Correct 17 ms 6488 KB Output is correct
9 Correct 1582 ms 6588 KB Output is correct
10 Correct 1584 ms 6592 KB Output is correct
11 Correct 1577 ms 6588 KB Output is correct
12 Incorrect 2 ms 6744 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 17 ms 6492 KB Output is correct
7 Correct 17 ms 6620 KB Output is correct
8 Correct 17 ms 6488 KB Output is correct
9 Incorrect 14 ms 11356 KB Output isn't correct
10 Halted 0 ms 0 KB -