oj.uz

Submission #257346

# Submission time Handle Problem Language Result Execution time Memory
257346 2020-08-04T06:40:19 Z BThero Intergalactic ship (IZhO19_xorsum) C++17
36 / 100
 2000 ms 33400 KB 
// chrono::system_clock::now().time_since_epoch().count()
#include<bits/stdc++.h>

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define debug(x) cerr << #x << " = " << x << endl;

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MAXN = (int)1e3 + 5;
const int MAXQ = (int)1e5 + 5;
const int MOD = (int)1e9 + 7;

int mem[4][MAXN][MAXN];
int seg[4][MAXN][MAXN];
int pw[MAXQ], _pw[MAXQ];
array<int, 3> que[MAXN];
int dp[MAXQ][2];
int arr[MAXN];
int n, q, ans;

int addMod(int a, int b, int m = MOD) {
  a += b;
  
  if (m <= a) {
    a -= m;
  }
  
  return a;
}

int mulMod(int a, int b, int m = MOD) {
  return a * 1ll * b % m;
}

int binPow(int a, int b, int m = MOD) {
  int ret = 1;
  
  while (b > 0) {
    if (b & 1) {
      ret = mulMod(ret, a, m);
    }
    
    a = mulMod(a, a, m);
    b >>= 1;
  }
  
  return ret;
}

int bit(int x, int p) {
  return (x >> p) & 1;
}

void pre() {
  pw[0] = _pw[0] = 1;
  
  for (int i = 1; i < MAXQ; ++i) {
    pw[i] = mulMod(pw[i - 1], 2);
    _pw[i] = binPow(pw[i], MOD - 2);
  } 
  
  dp[0][0] = 1;
  
  for (int i = 1; i < MAXQ; ++i) {
    for (int j = 0; j < 2; ++j) {
      dp[i][j] = addMod(dp[i - 1][0], dp[i - 1][1]);
    }
  }
}

int calc(int p1, int p2) {
  int ret = 0;
  
  for (int i = 0; i < 4; ++i) {
    for (int l = 1; l <= n; ++l) {
      for (int r = 1; r <= n; ++r) {
        seg[i][l][r] = 0;
        mem[i][l][r] = 0;
      }
    }
  }
  
  for (int i = 1; i <= q; ++i) {
    auto &[l, r, x] = que[i];
    int msk = 0;
    
    if (bit(x, p1)) {
      msk |= 1;
    }
    
    if (bit(x, p2)) {
      msk |= 2;
    }
    
    seg[msk][l][r]++;
  }
  
  for (int i = 0; i < 4; ++i) {
    for (int l = 1; l <= n; ++l) {
      int cur = 0;
    
      for (int r = n; r; --r) {
        cur = addMod(cur, seg[i][l][r]);
        mem[i][l][r] = addMod(mem[i][l - 1][r], cur);
      }
    }
  }

  for (int a = 1; a <= n; ++a) {
    for (int b = 1; b <= n; ++b) {
      array<int, 4> cnt = {0, 0, 0, 0};
      int bitA = bit(arr[a], p1);
      int bitB = bit(arr[b], p2);
      
      //for (int msk = 0; msk < 4; ++msk) {
        //int X = mem[msk][a][a];
        //int Y = mem[msk][b][b];
        //int Z = mem[msk][min(a, b)][max(a, b)];
        //X -= Z;
        //Y -= Z;
        //int left = mem[msk][n][1] - X - Y - Z;
        
        //if (bit(msk, 0)) {
          //cnt[1] += X;
        //}
        //else {
          //cnt[0] += X;
        //}
        
        //if (bit(msk, 1)) {
          //cnt[2] += Y;
        //}
        //else {
          //cnt[0] += Y;
        //}
        
        //if (bit(msk, 0) && bit(msk, 1)) {
          //cnt[3] += Z;
        //}
        //else {
          //cnt[0] += Z;
        //}
        
        //cnt[0] += left;
      //}
    
      for (int i = 1; i <= q; ++i) {
        auto &[l, r, k] = que[i];
        int msk = 0;
        
        if (l <= a && a <= r && bit(k, p1)) {
          msk |= 1;
        }
        
        if (l <= b && b <= r && bit(k, p2)) {
          msk |= 2;
        }
        
        cnt[msk]++;
      }
      
      int cur = 0;
      
      for (int x = 0; x < 2; ++x) {
        for (int y = 0; y < 2; ++y) {
          for (int z = 0; z < 2; ++z) {
            if ((bitA ^ x ^ z) == 1 && (bitB ^ y ^ z) == 1) {
              int tmp = 1;
              tmp = mulMod(tmp, dp[cnt[1]][x]);
              tmp = mulMod(tmp, dp[cnt[2]][y]);
              tmp = mulMod(tmp, dp[cnt[3]][z]);
              cur = addMod(cur, tmp);
            }
          }
        }
      }
      
      cur = mulMod(cur, pw[cnt[0]]);
      cur = mulMod(cur, mulMod(min(a, b), n - max(a, b) + 1));
      ret = addMod(ret, cur);
    }
  }
  
  return ret;
}

void solve() {
  scanf("%d", &n);
  
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &arr[i]);
  }
  
  scanf("%d", &q);
  
  for (int i = 1; i <= q; ++i) {
    int l, r, x;
    scanf("%d %d %d", &l, &r, &x);
    que[i] = {l, r, x};
  }
  
  for (int a = 0; a < 7; ++a) {
    for (int b = 0; b < 7; ++b) {
      ans = addMod(ans, mulMod(calc(a, b), (1 << (a + b))));
    }
  }
  
  printf("%d\n", ans);
}

int main() {
  int tt = 1;
  pre();
  
  while (tt--) {
    solve();
  }

  return 0;
}

Compilation message

xorsum.cpp: In function 'void solve()':
xorsum.cpp:196:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
xorsum.cpp:199:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &arr[i]);
     ~~~~~^~~~~~~~~~~~~~~
xorsum.cpp:202:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &q);
   ~~~~~^~~~~~~~~~
xorsum.cpp:206:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &l, &r, &x);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1920 KB Output is correct
2 Correct 20 ms 2040 KB Output is correct
3 Correct 20 ms 2168 KB Output is correct
4 Correct 20 ms 2304 KB Output is correct
5 Correct 21 ms 2168 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1920 KB Output is correct
2 Correct 20 ms 2040 KB Output is correct
3 Correct 20 ms 2168 KB Output is correct
4 Correct 20 ms 2304 KB Output is correct
5 Correct 21 ms 2168 KB Output is correct
6 Correct 64 ms 5120 KB Output is correct
7 Correct 63 ms 5112 KB Output is correct
8 Correct 68 ms 5120 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2076 ms 5624 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2094 ms 33400 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2808 KB Output is correct
2 Correct 29 ms 2816 KB Output is correct
3 Correct 26 ms 2816 KB Output is correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2808 KB Output is correct
2 Correct 29 ms 2816 KB Output is correct
3 Correct 26 ms 2816 KB Output is correct
4 Execution timed out 2044 ms 2960 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1920 KB Output is correct
2 Correct 20 ms 2040 KB Output is correct
3 Correct 20 ms 2168 KB Output is correct
4 Correct 20 ms 2304 KB Output is correct
5 Correct 21 ms 2168 KB Output is correct
6 Correct 64 ms 5120 KB Output is correct
7 Correct 63 ms 5112 KB Output is correct
8 Correct 68 ms 5120 KB Output is correct
9 Correct 26 ms 2808 KB Output is correct
10 Correct 29 ms 2816 KB Output is correct
11 Correct 26 ms 2816 KB Output is correct
12 Correct 906 ms 5240 KB Output is correct
13 Correct 892 ms 5240 KB Output is correct
14 Correct 691 ms 5112 KB Output is correct
15 Correct 901 ms 5112 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1920 KB Output is correct
2 Correct 20 ms 2040 KB Output is correct
3 Correct 20 ms 2168 KB Output is correct
4 Correct 20 ms 2304 KB Output is correct
5 Correct 21 ms 2168 KB Output is correct
6 Correct 64 ms 5120 KB Output is correct
7 Correct 63 ms 5112 KB Output is correct
8 Correct 68 ms 5120 KB Output is correct
9 Correct 26 ms 2808 KB Output is correct
10 Correct 29 ms 2816 KB Output is correct
11 Correct 26 ms 2816 KB Output is correct
12 Execution timed out 2044 ms 2960 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1920 KB Output is correct
2 Correct 20 ms 2040 KB Output is correct
3 Correct 20 ms 2168 KB Output is correct
4 Correct 20 ms 2304 KB Output is correct
5 Correct 21 ms 2168 KB Output is correct
6 Correct 64 ms 5120 KB Output is correct
7 Correct 63 ms 5112 KB Output is correct
8 Correct 68 ms 5120 KB Output is correct
9 Execution timed out 2076 ms 5624 KB Time limit exceeded
10 Halted 0 ms 0 KB -