Submission #219260

#	Time	Username	Problem	Language	Result	Execution time	Memory
219260		MKopchev	Secret (JOI14_secret)	C++14	100 / 100	522 ms	5240 KiB

secret

#include <bits/stdc++.h>
#include "secret.h"

using namespace std;
const int nmax=1e3+42;
/*
int Secret(int x,int y)
{
    //cout<<"Secret "<<x<<" "<<y<<endl;
    int ret;
    //cin>>ret;
    ret=x+y/2*2;

    //cout<<"ret= "<<ret<<endl;

    return ret;
}
*/
int n,inp[nmax];

map< pair<int,int>,int> seen;

void go(int l,int r)
{
     if(l==r)
     {
         seen[{l,r}]=inp[l];
         return;
     }

     int av=(l+r)/2;
     go(l,av);

     seen[{av,av}]=inp[av];

     for(int i=av-1;i>=l;i--)
        seen[{i,av}]=Secret(inp[i],seen[{i+1,av}]);

     go(av+1,r);
     for(int i=av+2;i<=r;i++)
        seen[{av+1,i}]=Secret(seen[{av+1,i-1}],inp[i]);
}
void Init(int N, int A[])
{
    n=N;
    for(int i=0;i<n;i++)inp[i]=A[i];

    go(0,n-1);
}

int solve(int l,int r,int lq,int rq)
{
    int av=(l+r)/2;
    if(rq<=av)return solve(l,av,lq,rq);
    if(av<lq)return solve(av+1,r,lq,rq);

    return Secret(seen[{lq,av}],seen[{av+1,rq}]);
}
int Query(int l,int r)
{
    if(seen.count({l,r}))return seen[{l,r}];
    return solve(0,n-1,l,r);
}
/*
int nnn=8,a[8]={1, 4, 7, 2, 5, 8, 3, 6};
int main()
{
    Init(nnn,a);
    cout<<Query(0,3)<<endl;//13
    cout<<Query(1,7)<<endl;//32
    cout<<Query(5,5)<<endl;//8
    cout<<Query(2,4)<<endl;//13
    return 0;
}
*/

• Subtask 1: 100 / 100