oj.uz

Submission #899111

# Submission time Handle Problem Language Result Execution time Memory
899111 2024-01-05T13:35:03 Z d4xn Intergalactic ship (IZhO19_xorsum) C++17
17 / 100
 2000 ms 11612 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 2 ms 6480 KB Output is correct
2 Correct 1 ms 6744 KB Output is correct
3 Correct 1 ms 6604 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 2 ms 6480 KB Output is correct
2 Correct 1 ms 6744 KB Output is correct
3 Correct 1 ms 6604 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6744 KB Output is correct
6 Correct 17 ms 6616 KB Output is correct
7 Correct 17 ms 6492 KB Output is correct
8 Correct 17 ms 6556 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 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 2066 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 1578 ms 6592 KB Output is correct
2 Correct 1587 ms 6596 KB Output is correct
3 Correct 1586 ms 6608 KB Output is correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1578 ms 6592 KB Output is correct
2 Correct 1587 ms 6596 KB Output is correct
3 Correct 1586 ms 6608 KB Output is correct
4 Incorrect 3 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 2 ms 6480 KB Output is correct
2 Correct 1 ms 6744 KB Output is correct
3 Correct 1 ms 6604 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6744 KB Output is correct
6 Correct 17 ms 6616 KB Output is correct
7 Correct 17 ms 6492 KB Output is correct
8 Correct 17 ms 6556 KB Output is correct
9 Correct 1578 ms 6592 KB Output is correct
10 Correct 1587 ms 6596 KB Output is correct
11 Correct 1586 ms 6608 KB Output is correct
12 Incorrect 67 ms 6900 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6480 KB Output is correct
2 Correct 1 ms 6744 KB Output is correct
3 Correct 1 ms 6604 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6744 KB Output is correct
6 Correct 17 ms 6616 KB Output is correct
7 Correct 17 ms 6492 KB Output is correct
8 Correct 17 ms 6556 KB Output is correct
9 Correct 1578 ms 6592 KB Output is correct
10 Correct 1587 ms 6596 KB Output is correct
11 Correct 1586 ms 6608 KB Output is correct
12 Incorrect 3 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 2 ms 6480 KB Output is correct
2 Correct 1 ms 6744 KB Output is correct
3 Correct 1 ms 6604 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6744 KB Output is correct
6 Correct 17 ms 6616 KB Output is correct
7 Correct 17 ms 6492 KB Output is correct
8 Correct 17 ms 6556 KB Output is correct
9 Incorrect 14 ms 11612 KB Output isn't correct
10 Halted 0 ms 0 KB -