Submission #784421

#TimeUsernameProblemLanguageResultExecution timeMemory
784421chanhchuong123Secret (JOI14_secret)C++14
100 / 100
418 ms4504 KiB
#include "secret.h" #include <bits/stdc++.h> using namespace std; const int MAX = 200200; int n; int a[MAX]; int mask[MAX]; int dp[18][MAX]; void divide(int l, int r, int level) { if (l == r) return; int mid = l + r >> 1; dp[level][mid] = a[mid]; dp[level][mid + 1] = a[mid + 1]; for (int i = mid - 1; i >= l; --i) dp[level][i] = Secret(a[i], dp[level][i + 1]); for (int i = mid + 2; i <= r; ++i) dp[level][i] = Secret(dp[level][i - 1], a[i]); for (int i = mid + 1; i <= r; ++i) mask[i] ^= 1 << level; divide(l, mid, level + 1); divide(mid + 1, r, level + 1); } void Init(int N, int A[]) { n = N; for (int i = 0; i < n; ++i) { a[i] = A[i]; mask[i] = 0; } divide(0, n - 1, 0); } int Query(int L, int R) { if (L == R) return a[L]; int lev = __builtin_ctz(mask[L] ^ mask[R]); return Secret(dp[lev][L], dp[lev][R]); }

Compilation message (stderr)

secret.cpp: In function 'void divide(int, int, int)':
secret.cpp:13:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   13 |     int mid = l + r >> 1;
      |               ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...