# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1101147 | InvMOD | Secret (JOI14_secret) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
//#include "secret.h"
using namespace std;
const int N = 1e3+1;
int mx_size, pref[N][N];
int Secret(int x, int y){
return min(x + ((y>>1)<<1), (int)1e9);
}
void Dnc(int l, int r, vector<int>& v){
if(l == r){
pref[l][l] = v[l];
return;
}
int m = l+r>>1;
pref[m][m] = v[m];
pref[m+1][m+1] = v[m+1];
for(int i = m-1; i >= l; i--){
pref[i][m] = Secret(v[i], pref[i+1][m]);
}
for(int i = m+2; i <= r; i++){
pref[m+1][i] = Secret(pref[m+1][i-1], v[i]);
}
Dnc(l, m, v);
Dnc(m+1, r, v);
return;
}
void Init(int n, int a[]){
vector<int> v;
for(int i = 0; i < n; i++){
v.push_back(a[i]);
}
--n; mx_size = n;
Dnc(0, n, v);
return;
}
int get(int l, int r, int Ql, int Qr){
if(l == r){
return pref[l][r];
}
else{
int m = l+r>>1;
if(Ql <= m && Qr > m){
return Secret(pref[Ql][m], pref[m+1][Qr]);
}
else{
if(Qr <= m){
return get(l, m, Ql, Qr);
}
else{
return get(m+1, r, Ql, Qr);
}
}
}
return -1;
}
int Query(int l, int r){
return get(0, mx_size, l, r);
}