oj.uz

Submission #396021

# Submission time Handle Problem Language Result Execution time Memory
396021 2021-04-29T11:32:57 Z rama_pang Intergalactic ship (IZhO19_xorsum) C++17
100 / 100
 1867 ms 14728 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
      vector<vector<int>> dpR(N + 2, vector<int>(N + 2)); //
      vector<vector<int>> dpL(N + 2, vector<int>(N + 2));
      vector<vector<int>> dpB(N + 2, vector<int>(N + 2));

      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 252 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 252 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 16 ms 332 KB Output is correct
7 Correct 18 ms 448 KB Output is correct
8 Correct 16 ms 332 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 2452 KB Output is correct
2 Correct 25 ms 648 KB Output is correct
3 Correct 17 ms 460 KB Output is correct
4 Correct 16 ms 332 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1714 ms 12408 KB Output is correct
2 Correct 1697 ms 12380 KB Output is correct
3 Correct 1689 ms 12472 KB Output is correct
4 Correct 1705 ms 12360 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 332 KB Output is correct
3 Correct 2 ms 332 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 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 7 ms 444 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 252 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 16 ms 332 KB Output is correct
7 Correct 18 ms 448 KB Output is correct
8 Correct 16 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 16 ms 460 KB Output is correct
13 Correct 16 ms 440 KB Output is correct
14 Correct 22 ms 444 KB Output is correct
15 Correct 16 ms 332 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 252 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 16 ms 332 KB Output is correct
7 Correct 18 ms 448 KB Output is correct
8 Correct 16 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 7 ms 444 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 16 ms 460 KB Output is correct
17 Correct 16 ms 440 KB Output is correct
18 Correct 22 ms 444 KB Output is correct
19 Correct 16 ms 332 KB Output is correct
20 Correct 539 ms 5800 KB Output is correct
21 Correct 534 ms 5708 KB Output is correct
22 Correct 447 ms 5468 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 252 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 16 ms 332 KB Output is correct
7 Correct 18 ms 448 KB Output is correct
8 Correct 16 ms 332 KB Output is correct
9 Correct 102 ms 2452 KB Output is correct
10 Correct 25 ms 648 KB Output is correct
11 Correct 17 ms 460 KB Output is correct
12 Correct 16 ms 332 KB Output is correct
13 Correct 1714 ms 12408 KB Output is correct
14 Correct 1697 ms 12380 KB Output is correct
15 Correct 1689 ms 12472 KB Output is correct
16 Correct 1705 ms 12360 KB Output is correct
17 Correct 2 ms 332 KB Output is correct
18 Correct 2 ms 332 KB Output is correct
19 Correct 2 ms 332 KB Output is correct
20 Correct 7 ms 444 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 16 ms 460 KB Output is correct
25 Correct 16 ms 440 KB Output is correct
26 Correct 22 ms 444 KB Output is correct
27 Correct 16 ms 332 KB Output is correct
28 Correct 539 ms 5800 KB Output is correct
29 Correct 534 ms 5708 KB Output is correct
30 Correct 447 ms 5468 KB Output is correct
31 Correct 1867 ms 14728 KB Output is correct
32 Correct 1861 ms 14688 KB Output is correct
33 Correct 1734 ms 14532 KB Output is correct
34 Correct 1808 ms 14404 KB Output is correct
35 Correct 1781 ms 14268 KB Output is correct
36 Correct 1775 ms 14540 KB Output is correct