oj.uz

Submission #599301

# Submission time Handle Problem Language Result Execution time Memory
599301 2022-07-19T12:30:50 Z Plurm Intergalactic ship (IZhO19_xorsum) C++11
17 / 100
 929 ms 1868 KB 
#include <bits/stdc++.h>
using namespace std;

int a[1024];
int qs[1024];
int qqs[1024];
int qqss[1024];
const int MOD = 1e9 + 7;
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", a + i);
  }
  int q;
  scanf("%d", &q);
  vector<tuple<int, int, int>> updates;
  for (int i = 0; i < q; i++) {
    int l, r, x;
    scanf("%d%d%d", &l, &r, &x);
    updates.push_back({l, r, x});
  }
  if (q <= 20) {
    int ans = 0;
    int last = 0;
    for (int bit = 0; bit < (1 << q); bit++) {
      for (int i = 0; i < q; i++) {
        if ((bit ^ last) & (1 << i)) {
          int l, r, x;
          tie(l, r, x) = updates[i];
          for (int j = l; j <= r; j++) {
            a[j] ^= x;
          }
        }
      }
      for (int i = 1; i <= n; i++) {
        qs[i] = (qs[i - 1] + a[i]) % MOD;
      }
      for (int i = 1; i <= n; i++) {
        qqs[i] = (qqs[i - 1] + qs[i]) % MOD;
        qqss[i] = (qqss[i - 1] + 1ll * qs[i] * qs[i] % MOD) % MOD;
      }
      for (int i = 1; i <= n; i++) {
        int k =
            (((qqss[n] + MOD - qqss[i - 1]) % MOD +
              (MOD - (2ll * qs[i - 1] * (qqs[n] + MOD - qqs[i - 1]) % MOD)) %
                  MOD) %
                 MOD +
             1ll * (n - i + 1) * qs[i - 1] % MOD * qs[i - 1] % MOD) %
            MOD;
        ans += k;
        ans %= MOD;
      }
      last = bit;
    }
    printf("%d\n", ans);
  }
  return 0;
}

Compilation message

xorsum.cpp: In function 'int main()':
xorsum.cpp:11:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
xorsum.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     scanf("%d", a + i);
      |     ~~~~~^~~~~~~~~~~~~
xorsum.cpp:16:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |   scanf("%d", &q);
      |   ~~~~~^~~~~~~~~~
xorsum.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     scanf("%d%d%d", &l, &r, &x);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 4 ms 212 KB Output is correct
7 Correct 4 ms 212 KB Output is correct
8 Correct 3 ms 308 KB Output is correct

Subtask #3
0 / 6.0

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

Subtask #4
0 / 9.0

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

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 918 ms 308 KB Output is correct
2 Correct 929 ms 288 KB Output is correct
3 Correct 905 ms 292 KB Output is correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 918 ms 308 KB Output is correct
2 Correct 929 ms 288 KB Output is correct
3 Correct 905 ms 292 KB Output is correct
4 Incorrect 2 ms 340 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 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 4 ms 212 KB Output is correct
7 Correct 4 ms 212 KB Output is correct
8 Correct 3 ms 308 KB Output is correct
9 Correct 918 ms 308 KB Output is correct
10 Correct 929 ms 288 KB Output is correct
11 Correct 905 ms 292 KB Output is correct
12 Incorrect 0 ms 212 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 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 4 ms 212 KB Output is correct
7 Correct 4 ms 212 KB Output is correct
8 Correct 3 ms 308 KB Output is correct
9 Correct 918 ms 308 KB Output is correct
10 Correct 929 ms 288 KB Output is correct
11 Correct 905 ms 292 KB Output is correct
12 Incorrect 2 ms 340 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 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 4 ms 212 KB Output is correct
7 Correct 4 ms 212 KB Output is correct
8 Correct 3 ms 308 KB Output is correct
9 Incorrect 21 ms 1868 KB Output isn't correct
10 Halted 0 ms 0 KB -