oj.uz

Submission #656564

# Submission time Handle Problem Language Result Execution time Memory
656564 2022-11-08T01:13:23 Z Tuanlinh123 Secret (JOI14_secret) C++17
100 / 100
 436 ms 4868 KB 
#include "secret.h"
#include <bits/stdc++.h>
using namespace std;

map <pair<int, int>, int> Map;
int a[1005], NN;

void prep(int l, int r)
{
    if (r-l<=1)
        return;
    int mid=(l+r)/2;
    int crr=a[mid-1];
    for (int i=mid-2; i>=l; i--)
    {
        crr=Secret(a[i], crr);
        Map[{i, mid-1}]=crr;
    }
    crr=a[mid];
    for (int i=mid+1; i<=r; i++)
    {
        crr=Secret(crr, a[i]);
        Map[{mid, i}]=crr;
    }
    prep(l, mid-1);
    prep(mid+1, r);
}

void Init(int n, int A[])
{
    NN=n;
    for (int i=0; i<n; i++)
    {
        a[i]=A[i];
        Map[{i, i}]=a[i];
    }
    prep(0, n-1);
}

int Find(int L, int R, int tl, int tr)
{
    int mid=(L+R)/2;
    if (mid>=tl && mid<=tr)
        return mid;
    if (mid<tl)
        return Find(mid+1, R, tl, tr);
    return Find(L, mid-1, tl, tr);
}

int Query(int L, int R)
{
    if (L==R)
        return a[L];
    if (L+1==R)
        return Secret(a[L], a[R]);
    int mid=Find(0, NN-1, L, R);
    if (mid==L)
        return Map[{mid, R}];
    return Secret(Map[{L, mid-1}], Map[{mid, R}]);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 2592 KB Output is correct - number of calls to Secret by Init = 3331, maximum number of calls to Secret by Query = 1
2 Correct 123 ms 2636 KB Output is correct - number of calls to Secret by Init = 3339, maximum number of calls to Secret by Query = 1
3 Correct 123 ms 2644 KB Output is correct - number of calls to Secret by Init = 3347, maximum number of calls to Secret by Query = 1
4 Correct 432 ms 4868 KB Output is correct - number of calls to Secret by Init = 7467, maximum number of calls to Secret by Query = 1
5 Correct 436 ms 4868 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
6 Correct 425 ms 4756 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
7 Correct 426 ms 4836 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
8 Correct 428 ms 4812 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
9 Correct 434 ms 4788 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
10 Correct 425 ms 4824 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1