oj.uz

Submission #898244

# Submission time Handle Problem Language Result Execution time Memory
898244 2024-01-04T11:59:46 Z vjudge1 Intergalactic ship (IZhO19_xorsum) C++17
9 / 100
 2000 ms 11612 KB 
#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];
        sum %= mod;
        
        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 6488 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 6744 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 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 6744 KB Output is correct
6 Correct 26 ms 6492 KB Output is correct
7 Correct 25 ms 6608 KB Output is correct
8 Correct 25 ms 6616 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 11612 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 2049 ms 6492 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

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

Subtask #6
0 / 11.0

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

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 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 6744 KB Output is correct
6 Correct 26 ms 6492 KB Output is correct
7 Correct 25 ms 6608 KB Output is correct
8 Correct 25 ms 6616 KB Output is correct
9 Execution timed out 2045 ms 6492 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 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 6744 KB Output is correct
6 Correct 26 ms 6492 KB Output is correct
7 Correct 25 ms 6608 KB Output is correct
8 Correct 25 ms 6616 KB Output is correct
9 Execution timed out 2045 ms 6492 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 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 6744 KB Output is correct
6 Correct 26 ms 6492 KB Output is correct
7 Correct 25 ms 6608 KB Output is correct
8 Correct 25 ms 6616 KB Output is correct
9 Incorrect 18 ms 11612 KB Output isn't correct
10 Halted 0 ms 0 KB -