oj.uz

Submission #903935

# Submission time Handle Problem Language Result Execution time Memory
903935 2024-01-11T14:52:11 Z LucaLucaM Intergalactic ship (IZhO19_xorsum) C++17
17 / 100
 2000 ms 2816 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstring>
#warning That's the baby, that's not my baby
#define int long long

typedef long long ll;

const int mod = 1e9 + 7;

struct Update {
  int l, r, x;
};

int power(int a, int b) {
  int p = 1;
  while (b) {
    if (b & 1) {
      p = (ll) p * a % mod;
    }
    a = (ll) a * a % mod;
    b >>= 1;
  }
  return p;
}

int solve(std::vector<int> a) {
  int n = (int) a.size();

  ll ret = 0;
  ll before = 0;

  for (int i = 0; i < n; i++) {
    ret += (ll) a[i] * a[i] * (i + 1) * (n - i);
    ret += (ll) a[i] * (n - i) * before;
    before += (ll) 2 * a[i] * (i + 1);
  }
  return ret % mod;
}

signed main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);

  int n;
  std::cin >> n;
  std::vector<int> a(n);
  for (auto &x : a) {
    std::cin >> x;
  }

  int q;
  std::cin >> q;

  std::vector<Update> Q(q);

  for (auto &[l, r, x] : Q) {
    std::cin >> l >> r >> x;
    --l, --r;
  }

  ll answer = 0;

  for (int mask = 0; mask < (1 << q); mask++) {
    std::vector<int> b = a;
    for (int i = 0; i < q; i++) {
      if (mask & (1 << i)) {
        for (int k = Q[i].l; k <= Q[i].r; k++) {
          b[k] ^= Q[i].x;
        }
      }
    }
    answer += solve(b);
  }

  std::cout << answer % mod;


  return 0;
}

Compilation message

xorsum.cpp:6:2: warning: #warning That's the baby, that's not my baby [-Wcpp]
    6 | #warning That's the baby, that's not my baby
      |  ^~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 416 KB Output is correct
4 Correct 1 ms 500 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
5.0 / 5.0

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

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 2816 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 2064 ms 348 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 432 KB Output is correct
2 Correct 253 ms 428 KB Output is correct
3 Correct 260 ms 428 KB Output is correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 432 KB Output is correct
2 Correct 253 ms 428 KB Output is correct
3 Correct 260 ms 428 KB Output is correct
4 Incorrect 5 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 416 KB Output is correct
4 Correct 1 ms 500 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 277 ms 432 KB Output is correct
10 Correct 253 ms 428 KB Output is correct
11 Correct 260 ms 428 KB Output is correct
12 Incorrect 11 ms 464 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 416 KB Output is correct
4 Correct 1 ms 500 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 277 ms 432 KB Output is correct
10 Correct 253 ms 428 KB Output is correct
11 Correct 260 ms 428 KB Output is correct
12 Incorrect 5 ms 348 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 416 KB Output is correct
4 Correct 1 ms 500 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Incorrect 16 ms 2816 KB Output isn't correct
10 Halted 0 ms 0 KB -