oj.uz

Submission #487513

# Submission time Handle Problem Language Result Execution time Memory
487513 2021-11-15T18:40:51 Z MohamedFaresNebili Secret (JOI14_secret) C++14
100 / 100
 437 ms 8516 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
#include "secret.h"

        using namespace std;

        using ll  = long long;
        using vi  = vector<int>;

        #define pb push_back
        #define ff first
        #define ss second
        #define lb lower_bound
        #define all(x) (x).begin() , (x).end()

        int st[2555][2555], arr[2555], n;

        void build(int L, int R) {
            int md = (L + R)/2;
            st[md][md] = arr[md];
            st[md + 1][md + 1] = arr[md + 1];
            for(int l = md + 2; l <= R; l++)
                st[md + 1][l] = Secret(st[md + 1][l - 1], arr[l]);
            for(int l = md - 1; l >= L; l--)
                st[md][l] = Secret(arr[l], st[md][l+1]);
            if(L < md) build(L, md);
            if(md + 1 < R) build(md + 1, R);
        }
        void Init(int N, int A[]) {
            n = N;
            for(int l = 0; l < n; l++) arr[l] = A[l];
            build(0, n-1);
        }
        int Query(int L, int R) {
            int l = 0, r = n - 1;
            while(l != r) {
                int md = (l+r)/2;
                if(md >= L && md < R)
                    return Secret(st[md][L], st[md+1][R]);
                else if(md == R) return st[md][L];
                else if(md < L) l = md + 1;
                else r = md;
            }
            return st[l][l];
        }

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 4544 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 122 ms 4448 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 121 ms 4424 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 431 ms 8348 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 428 ms 8412 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 437 ms 8392 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 431 ms 8392 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 429 ms 8468 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 432 ms 8388 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 429 ms 8516 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1