oj.uz

Submission #219260

# Submission time Handle Problem Language Result Execution time Memory
219260 2020-04-04T20:43:25 Z MKopchev Secret (JOI14_secret) C++14
100 / 100
 522 ms 5240 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 2812 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 149 ms 2680 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 150 ms 2680 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 515 ms 5168 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 511 ms 4856 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 506 ms 4860 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 513 ms 5240 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 521 ms 4856 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 522 ms 4856 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 510 ms 4984 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1