oj.uz

Submission #396025

# Submission time Handle Problem Language Result Execution time Memory
396025 2021-04-29T11:34:38 Z rama_pang Intergalactic ship (IZhO19_xorsum) C++17
100 / 100
 1654 ms 13380 KB 
#include <bits/stdc++.h>
using namespace std;

template<int MOD>
class ModInt {
 public:
  int v;

  ModInt() : v(0) {}
  ModInt(long long _v) {
    v = int((-MOD < _v && _v < MOD) ? (_v) : (_v % MOD));
    if (v < 0) v += MOD; }

  friend bool operator==(const ModInt &a, const ModInt &b) { return a.v == b.v; }
  friend bool operator!=(const ModInt &a, const ModInt &b) { return a.v != b.v; }
  friend bool operator<(const ModInt &a, const ModInt &b) { return a.v < b.v; }
  friend bool operator<=(const ModInt &a, const ModInt &b) { return a.v <= b.v; }
  friend bool operator>(const ModInt &a, const ModInt &b) { return a.v > b.v; }
  friend bool operator>=(const ModInt &a, const ModInt &b) { return a.v >= b.v; }

  ModInt& operator+=(const ModInt &a) {
    if ((v += a.v) >= MOD) v -= MOD;
    return *this; }
  ModInt& operator-=(const ModInt &a) {
    if ((v -= a.v) < 0) v += MOD;
    return *this; }
  ModInt& operator*=(const ModInt &a) {
    v = 1ll * v * a.v % MOD;
    return *this; }
  ModInt& operator/=(const ModInt &a) {
    return (*this) *= inverse(a); }

  friend ModInt pow(ModInt a, long long x) {
    ModInt res = 1; assert(x >= 0);
    for (; x; x /= 2, a *= a) if (x & 1) res *= a;
    return res; }
  friend ModInt inverse(ModInt a) {
    assert(a.v != 0);
    return pow(a, MOD - 2); }

  ModInt operator+() const { return ModInt(v); }
  ModInt operator-() const { return ModInt(-v); }
  ModInt operator++() const { return *this += 1; }
  ModInt operator--() const { return *this -= 1; }

  friend ModInt operator+(ModInt a, const ModInt &b) { return a += b; }
  friend ModInt operator-(ModInt a, const ModInt &b) { return a -= b; }
  friend ModInt operator*(ModInt a, const ModInt &b) { return a *= b; }
  friend ModInt operator/(ModInt a, const ModInt &b) { return a /= b; }

  friend istream& operator>>(istream &is, ModInt &v) { is >> v.v; return is; }
  friend ostream& operator<<(ostream &os, const ModInt &v) { os << v.v; return os; }
};

const int MOD = 1e9 + 7;
using Mint = ModInt<MOD>;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  const int M = 128;

  int N;
  cin >> N;

  vector<int> A(N + 1);
  for (int i = 1; i <= N; i++) {
    cin >> A[i];
  }

  int Q;
  cin >> Q;

  vector<int> L(Q), R(Q), K(Q);
  for (int i = 0; i < Q; i++) {
    cin >> L[i] >> R[i] >> K[i];
  }

  Mint answer = 0;
  for (int a = 0; a < 7; a++) { // a-th bit of left endpoint
    for (int b = 0; b < 7; b++) { // b-th bit of right endpoint
      static vector<vector<int>> dpR(N + 2, vector<int>(N + 2));
      static vector<vector<int>> dpL(N + 2, vector<int>(N + 2));
      static vector<vector<int>> dpB(N + 2, vector<int>(N + 2));

      for (int i = 0; i <= N + 1; i++) {
        for (int j = 0; j <= N + 1; j++) {
          dpR[i][j] = dpL[i][j] = dpB[i][j] = 0;
        }
      }

      const auto AddRect = [&](vector<vector<int>> &s, int a, int b, int c, int d) { // (a, b) to (c, d)
        s[a][b] += 1;
        s[a][d + 1] -= 1;
        s[c + 1][b] -= 1;
        s[c + 1][d + 1] += 1;
      };

      for (int i = 0; i < Q; i++) {
        bool inA = (K[i] >> a) & 1;
        bool inB = (K[i] >> b) & 1;
        if (inA && inB) {
          // Affect only right: [1, L[i]-1] * [L[i], R[i]]
          AddRect(dpR, 1, L[i], L[i] - 1, R[i]);
          // Affect only left : [L[i], R[i]] * [R[i] + 1, N]
          AddRect(dpL, L[i], R[i] + 1, R[i], N);
          // Affect both      : [L[i], R[i]] * [L[i], R[i]]
          AddRect(dpB, L[i], L[i], R[i], R[i]);
        } else if (inA) {
          // Affect only left : [L[i], R[i]] * [L[i], N]
          AddRect(dpL, L[i], 1, R[i], N);
        } else if (inB) {
          // Affect only right: [1, R[i]] * [L[i], R[i]]
          AddRect(dpR, 1, L[i], N, R[i]);
        }
      }

      for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
          dpL[i][j] += dpL[i - 1][j] + dpL[i][j - 1] - dpL[i - 1][j - 1];
          dpR[i][j] += dpR[i - 1][j] + dpR[i][j - 1] - dpR[i - 1][j - 1];
          dpB[i][j] += dpB[i - 1][j] + dpB[i][j - 1] - dpB[i - 1][j - 1];
        }
      }

      const auto Get = [&](int x, int parity) -> int {
        return x == 0 ? (parity == 0) : ((MOD + 1) / 2);
      };

      for (int i = 1; i <= N; i++) {
        for (int j = i; j <= N; j++) {
          int initL = (A[i] >> a) & 1;
          int initR = (A[j] >> b) & 1;
          Mint mul = Mint(1 + (i != j)) * i * (N - j + 1) * (1 << a) * (1 << b);
          for (int tl = 0; tl < 2; tl++) { // toggle left even/odd times
            for (int tr = 0; tr < 2; tr++) { // toggle right even/odd times
              for (int tb = 0; tb < 2; tb++) { // toggle both even/odd times
                if ((initL ^ tl ^ tb) == 1 && (initR ^ tr ^ tb) == 1) { // both bits are on
                  answer += mul * Get(dpL[i][j], tl) * Get(dpR[i][j], tr) * Get(dpB[i][j], tb);
                }
              }
            }
          }
        }
      }
    }
  }

  for (int i = 1; i <= Q; i++) answer *= 2;

  cout << answer << '\n';
  return 0;
}

Compilation message

xorsum.cpp: In function 'int main()':
xorsum.cpp:62:13: warning: unused variable 'M' [-Wunused-variable]
   62 |   const int M = 128;
      |             ^

Subtask #1
4.0 / 4.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 16 ms 444 KB Output is correct
7 Correct 16 ms 440 KB Output is correct
8 Correct 15 ms 456 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 1632 KB Output is correct
2 Correct 24 ms 564 KB Output is correct
3 Correct 16 ms 332 KB Output is correct
4 Correct 16 ms 444 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1488 ms 12192 KB Output is correct
2 Correct 1469 ms 12192 KB Output is correct
3 Correct 1458 ms 12228 KB Output is correct
4 Correct 1453 ms 12180 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 204 KB Output is correct
3 Correct 2 ms 204 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 204 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 6 ms 332 KB Output is correct
5 Correct 6 ms 332 KB Output is correct
6 Correct 6 ms 332 KB Output is correct
7 Correct 6 ms 332 KB Output is correct

Subtask #7
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 16 ms 444 KB Output is correct
7 Correct 16 ms 440 KB Output is correct
8 Correct 15 ms 456 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 204 KB Output is correct
11 Correct 2 ms 204 KB Output is correct
12 Correct 15 ms 448 KB Output is correct
13 Correct 15 ms 332 KB Output is correct
14 Correct 16 ms 332 KB Output is correct
15 Correct 16 ms 452 KB Output is correct

Subtask #8
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 16 ms 444 KB Output is correct
7 Correct 16 ms 440 KB Output is correct
8 Correct 15 ms 456 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 204 KB Output is correct
11 Correct 2 ms 204 KB Output is correct
12 Correct 6 ms 332 KB Output is correct
13 Correct 6 ms 332 KB Output is correct
14 Correct 6 ms 332 KB Output is correct
15 Correct 6 ms 332 KB Output is correct
16 Correct 15 ms 448 KB Output is correct
17 Correct 15 ms 332 KB Output is correct
18 Correct 16 ms 332 KB Output is correct
19 Correct 16 ms 452 KB Output is correct
20 Correct 498 ms 4500 KB Output is correct
21 Correct 489 ms 4420 KB Output is correct
22 Correct 405 ms 4428 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 16 ms 444 KB Output is correct
7 Correct 16 ms 440 KB Output is correct
8 Correct 15 ms 456 KB Output is correct
9 Correct 102 ms 1632 KB Output is correct
10 Correct 24 ms 564 KB Output is correct
11 Correct 16 ms 332 KB Output is correct
12 Correct 16 ms 444 KB Output is correct
13 Correct 1488 ms 12192 KB Output is correct
14 Correct 1469 ms 12192 KB Output is correct
15 Correct 1458 ms 12228 KB Output is correct
16 Correct 1453 ms 12180 KB Output is correct
17 Correct 2 ms 332 KB Output is correct
18 Correct 2 ms 204 KB Output is correct
19 Correct 2 ms 204 KB Output is correct
20 Correct 6 ms 332 KB Output is correct
21 Correct 6 ms 332 KB Output is correct
22 Correct 6 ms 332 KB Output is correct
23 Correct 6 ms 332 KB Output is correct
24 Correct 15 ms 448 KB Output is correct
25 Correct 15 ms 332 KB Output is correct
26 Correct 16 ms 332 KB Output is correct
27 Correct 16 ms 452 KB Output is correct
28 Correct 498 ms 4500 KB Output is correct
29 Correct 489 ms 4420 KB Output is correct
30 Correct 405 ms 4428 KB Output is correct
31 Correct 1654 ms 13376 KB Output is correct
32 Correct 1598 ms 13372 KB Output is correct
33 Correct 1538 ms 13376 KB Output is correct
34 Correct 1592 ms 13372 KB Output is correct
35 Correct 1566 ms 13380 KB Output is correct
36 Correct 1570 ms 13376 KB Output is correct