Submission #637179

#TimeUsernameProblemLanguageResultExecution timeMemory
637179Blobo2_Blobo2Secret (JOI14_secret)C++17
6 / 100
1533 ms39464 KiB
#include "secret.h" #include <bits/stdc++.h> using namespace std; int seg[4000],n,arr[1000],cnt=0; void update(int idx=1,int l=0,int r = n-1){ if(l == r){ seg[idx] = arr[l]; return; } int mid = (l+r)>>1; update(idx<<1,mid+1,r); update(idx<<1|1,l,mid); seg[idx] = Secret(seg[idx<<1|1], seg[idx<<1]); //cout<<l<<' '<<r<<' '<<seg[idx<<1]<<' '<<seg[idx<<1|1]<<' '<<seg[idx]<<endl; } map<pair<int,int>,int>mp; int query(int L,int R,int idx=1,int l=0,int r=n-1){ if(l >= L && r <= R)return seg[idx]; if(r < L || l > R)return -1; int mid = (l+r)>>1; int first = query(L,R,idx<<1,mid+1,r); int second = query(L,R,idx<<1|1,l,mid); if(first != -1 && second != -1){ if(mp.find({second,first}) == mp.end()) return mp[{second,first}] = Secret(second,first); else return mp[{second,first}]; } else if(first != -1) return first; else if(second != -1) return second; else return -1; } int dp[1000][1000]; void Init(int N,int A[]){ n = N; for(int i=0;i<n;i++)arr[i] = A[i]; update(); for(int i=0;i<n;i++){ for(int j=i;j<n;j++){ dp[i][j] = query(i,j); } } } int Query(int l,int r){ return dp[l][r]; }
#Verdict Execution timeMemoryGrader output
Fetching results...