# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1179796 | paulxaxa | Secret (JOI14_secret) | C++17 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "secret.h"
#define NMAX 1000
#define LOG 9
#define ll long long int
#define BASE 32
#define MOD 998244353
using namespace std;
ifstream fin("cod.in");
ofstream fout("cod.out");
int Secret(int X,int Y)
{
return min(X + (Y/2)*2,1000000000);
}
int pref[NMAX+1][NMAX+1];
int n;
int a[NMAX+1];
void divide(int st,int dr)
{
int m = (st+dr)/2;
pref[m][m] = a[m];
for(int i=m-1;i>=st;i--)
{
pref[i][m] = Secret(a[i],pref[i+1][m]);
}
pref[m+1][m+1] = a[m+1];
for(int i=m+2;i<=dr;i++)
{
pref[m+1][i] = Secret(pref[m+1][i-1],a[i]);
}
if(st<m)
{
divide(st,m);
}
if(m+1<dr)
{
divide(m+1,dr);
}
}
void Init(int N,int A[])
{
n=N;
for(int i=1;i<=n;i++)
{
a[i] = A[i-1];
}
divide(1,N);
}
int Query(int L,int R)
{
int st=1;
int dr=n;
L++;
R++;
while(st<dr)
{
int m = (st+dr)/2;
if(L<=m && m+1<=R)
{
return Secret(pref[L][m],pref[m+1][R]);
}
if(R<=m)
{
dr=m;
}
else
{
st=m+1;
}
}
return pref[st][st];
}
//int main()
//{
// int N;
// cin >> N;
// int A[100];
// for(int i=0;i<N;i++)
// {
// cin >> A[i];
// }
// Init(N,A);
// int q;
// cin >> q;
// while(q--)
// {
// int l,r;
// cin >> l >> r;
// cout << Query(l,r) << '\n';
// }
//}