Submission #1213447

#TimeUsernameProblemLanguageResultExecution timeMemory
1213447MalixSecret (JOI14_secret)C++20
0 / 100
20092 ms4600 KiB
#include "secret.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<vi> vii; typedef pair<int,int> pi; typedef vector<pi> pii; typedef tuple<int,int,int> ti; typedef vector<ll> li; typedef vector<li> lii; #define REP(i,a,b) for(int i=a;i<b;i++) #define F first #define S second #define PB push_back #define LSOne(s) ((s)&(-s)) ll INF=1000000000000000010; int inf=1e9+10; ll M=1e9+7; map<pi,int> mp; vi a; int n; set<pi> st; void solve(int l,int r){ if(l==r)return; if(l+1==r){ mp[{l,r}]=Secret(a[l],a[r]); return; } int m=(l+r)/2; solve(0,m); solve(m+1,r); int c=a[m]; for(int i=m-1;i>=l;i--){ if(st.count({i,m})==0){ mp[{i,m}]=Secret(a[i],c); c=mp[{i,m}]; st.insert({i,m}); } else c=mp[{i,m}]; } c=a[m+1]; REP(i,m+2,r+1){ if(st.count({m+1,i})==0){ mp[{m+1,i}]=Secret(c,a[i]); c=mp[{m+1,i}]; st.insert({m+1,i}); } else c=mp[{m+1,i}]; } } void Init(int N, int A[]) { n=N; a.resize(n); REP(i,0,n){ a[i]=A[i]; mp[{i,i}]=A[i]; st.insert({i,i}); } solve(0,n-1); } int Query(int L, int R) { auto it=st.lower_bound({L+1,0}); it=prev(it); int m=it->S; return Secret(mp[{L,m}],mp[{m+1,R}]); }
#Verdict Execution timeMemoryGrader output
Fetching results...