Submission #620609

#TimeUsernameProblemLanguageResultExecution timeMemory
620609radalSecret (JOI14_secret)C++17
6 / 100
536 ms12488 KiB
#include <bits/stdc++.h> #include "secret.h" #pragma GCC target("sse,sse2") #pragma GCC optimize("unroll-loops,O2") #define rep(i,l,r) for (int i = l; i < r; i++) #define repr(i,r,l) for (int i = r; i >= l; i--) #define X first #define Y second #define all(x) (x).begin() , (x).end() #define pb push_back #define endl '\n' #define debug(x) cerr << #x << " : " << x << endl; using namespace std; typedef long long ll; typedef long double ld; typedef pair<int,int> pll; constexpr int N = 1e3+10,mod = 998244353,inf = 1e9+10; inline int mkay(int a,int b){ if (a+b >= mod) return a+b-mod; if (a+b < 0) return a+b+mod; return a+b; } inline int poww(int a,int k){ if (k < 0) return 0; int z = 1; while (k){ if (k&1) z = 1ll*z*a%mod; a = 1ll*a*a%mod; k /= 2; } return z; } int a[N],n; int seg[N*4][N][2]; void build(int l,int r,int v = 1){ if (r-l == 1){ seg[v][1][0] = seg[v][1][1] = a[l]; return; } int u = (v << 1),m = (l+r) >> 1; build(l,m,u); build(m,r,u|1); if (v == 1) return; int sz1 = m-l,sz2 = r-m; rep(i,1,sz1+1){ seg[v][i][0] = seg[u][i][0]; seg[v][i+sz2][1] = Secret(seg[u][i][1],seg[u|1][sz2][0]); } rep(i,1,sz2+1){ seg[v][i+sz1][0] = Secret(seg[u][sz1][0],seg[u|1][i][0]); seg[v][i][1] = seg[u|1][i][1]; } } int que(int l,int r,int s,int e,int v = 1){ int u = (v << 1),m = (l+r) >> 1; if (e <= m) return que(l,m,s,e,u); if (s >= m) return que(m,r,s,e,u|1); return Secret(seg[u][m-s][1],seg[u|1][e-m][0]); } void Init(int nn,int A[]){ n = nn; rep(i,0,n) a[i] = A[i]; build(0,n); } int Query(int l, int r){ r++; if (r == l+1){ return a[l]; } return que(0,n,l,r); }
#Verdict Execution timeMemoryGrader output
Fetching results...