Submission #576001

#TimeUsernameProblemLanguageResultExecution timeMemory
576001talant117408Secret (JOI14_secret)C++17
100 / 100
460 ms12312 KiB
#include "secret.h" #include <bits/stdc++.h> #ifndef EVAL #include "grader.cpp" #endif using namespace std; typedef long long ll; typedef pair <int, int> pii; typedef pair <ll, ll> pll; #define pb push_back #define mp make_pair #define lb lower_bound #define ub upper_bound #define endl '\n' #define all(v) (v).begin(),(v).end() #define sz(v) int((v).size()) #define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); const int MAXN = 1e3+3; int LL[MAXN][MAXN], RR[MAXN][MAXN], V[MAXN]; int n; void dnc(int l, int r) { if (l > r) return; int mid = (l+r) >> 1; LL[mid][mid] = V[mid]; if (l == r) { return; } RR[mid][mid+1] = V[mid+1]; for (int i = mid-1; i >= l; i--) { LL[mid][i] = Secret(V[i], LL[mid][i+1]); } for (int i = mid+2; i <= r; i++) { RR[mid][i] = Secret(RR[mid][i-1], V[i]); } dnc(l, mid); dnc(mid+1, r); } void Init(int N, int A[]) { n = N; for (int i = 0; i < n; i++) { V[i] = A[i]; } dnc(0, n-1); } int get(int l, int r, int ql, int qr) { if (l == r) return V[l]; if (l > r) return 0; int mid = (l+r) >> 1; if (l <= ql && qr <= r && ql <= mid && mid < qr) { return Secret(LL[mid][ql], RR[mid][qr]); } if (ql > mid) return get(mid+1, r, ql, qr); else return get(l, mid, ql, qr); } int Query(int L, int R) { return get(0, n-1, L, R); }
#Verdict Execution timeMemoryGrader output
Fetching results...