Submission #901698

#TimeUsernameProblemLanguageResultExecution timeMemory
901698trMatherzSecret (JOI14_secret)C++17
0 / 100
359 ms4436 KiB
//#include <iostream> //cin, cout #include "secret.h" /* #include <fstream> std::ifstream cin ("ex.in"); std::ofstream cout ("ex.out"); */ // includes #include <cmath> #include <set> #include <map> #include <queue> #include <string> #include <vector> #include <array> #include <algorithm> #include <numeric> #include <iomanip> #include <unordered_set> #include <stack> #include <ext/pb_ds/assoc_container.hpp> #include <random> #include <chrono> //usings using namespace std; using namespace __gnu_pbds; // misc #define ll long long #define pb push_back #define pq priority_queue #define ub upper_bound #define lb lower_bound template<typename T, typename U> bool emin(T &a, const U &b){ return b < a ? a = b, true : false; } template<typename T, typename U> bool emax(T &a, const U &b){ return b > a ? a = b, true : false; } typedef uint64_t hash_t; // vectors #define vi vector<int> #define vvi vector<vi> #define vvvi vector<vvi> #define vpii vector<pair<int, int>> #define vvpii vector<vector<pair<int, int>>> #define vppipi vector<pair<int, pair<int, int>>> #define vl vector<ll> #define vvl vector<vl> #define vvvl vector<vvl> #define vpll vector<pair<ll, ll>> #define vb vector<bool> #define vvb vector<vb> #define vs vector<string> #define sz(x) (int)x.size() #define rz resize #define all(x) x.begin(), x.end() // pairs #define pii pair<int, int> #define pll pair<ll, ll> #define mp make_pair #define f first #define s second // sets #define si set<int> #define sl set<ll> #define ss set<string> #define in insert template <class T> using iset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; // maps #define mii map<int, int> #define mll map<ll, ll> // loops #define FR(x, z, y) for (int x = z; x < y; x++) #define FRe(x, z, y) FR(x, z, y + 1) #define F(x, y) FR(x, 0, y) #define Fe(x, y) F(x, y + 1) #define A(x, y) for(auto &x : y) int n; vvi v; vi g, a; void go(int l, int r, int x){ if(l == r) return; int m = (l + r) / 2; v[x][m] = a[m]; for(int i = m - 1; i >= l; i--) v[x][i] = Secret(v[x][i + 1], a[i]); v[x][m + 1] = a[m + 1]; for(int i = m + 2; i <= r; i++) v[x][i] = Secret(v[x][i - 1], a[i]); for(int i = m + 1; i <= r; i++) g[i] ^= 1 << x; go(l, m, x + 1); go(m + 1, r, x + 1); } void Init(int N, int A[]){ n = N; v = vvi(10, vi(n)); a = g = vi(n); F(i, n) a[i] = A[i]; go(0, n - 1, 0); } int Query(int L, int R){ if(L == R) return a[L]; int bits = __builtin_ctz(g[L] ^ g[R]); return Secret(v[bits][L], v[bits][R]); }
#Verdict Execution timeMemoryGrader output
Fetching results...