oj.uz

Submission #931838

# Submission time Handle Problem Language Result Execution time Memory
931838 2024-02-22T11:57:59 Z Muaath_5 Secret (JOI14_secret) C++17
100 / 100
 378 ms 6544 KB 
    /*
     
    Debugger/Idea: Ahmad Alhashim (@vahmad)
     
    */
    #include <bits/stdc++.h>
    #include "secret.h"
    #define ll long long
    using namespace std;
     
    //const int N = 2001;
    const int DST_LOG = 12, DST_SIZE = (1 << DST_LOG);
     
    int Secret(int X, int Y);
    void Init(int N, int A[]);
    int Query(int L, int R);
     
    int n, a[DST_SIZE], dst[DST_LOG][DST_SIZE];
     
     
    //#define __lg(x) ceil(log2(x))
    map<pair<int, int>, int> ans;
	int sec(int x, int y) {
     if (ans.count({x, y}))
       	return ans[{x, y}];
      return ans[{x, y}] = Secret(x, y);
    }
     
    void build_rec(int l, int r, int lvl)
    {
        const int md = (l + r) / 2;
        dst[lvl][md] = a[md];
        for (int i = md + 1; i < r; i++) {
            dst[lvl][i] = sec(dst[lvl][i - 1], a[i]);
        }
        dst[lvl][md - 1] = a[md - 1];
        for (int i = md - 2; i >= l; i--) {
            dst[lvl][i] = sec(a[i], dst[lvl][i + 1]);
        }
        if (lvl == 0) return;
        build_rec(l, md, lvl - 1);
        build_rec(md, r, lvl - 1);
    }
     
    void build() {
        int levels_count = __lg(n);
        build_rec(0, (1 << (levels_count + 1)), levels_count);
    }
     
    int query(int l, int r)
    {
        const int lvl = 31 - __builtin_clz(l ^ r);
        if (l == r) return a[l];
        int res = sec(dst[lvl][l], dst[lvl][r]);
        return res;
    }
     
     
    void Init(int N, int A[])
    {
        n = N;
        for (int i = 0; i < N; i++) {
            a[i] = A[i];
        }
        build();
    }
     
    map<pair<int, int>, int> mp;
    int Query(int L, int R)
    {
        if (mp.find({L, R}) == mp.end())
            return mp[{L, R}] = query(L, R);
        return mp[{L, R}];
    }

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 4004 KB Output is correct - number of calls to Secret by Init = 3332, maximum number of calls to Secret by Query = 1
2 Correct 111 ms 4180 KB Output is correct - number of calls to Secret by Init = 3843, maximum number of calls to Secret by Query = 1
3 Correct 110 ms 4008 KB Output is correct - number of calls to Secret by Init = 3848, maximum number of calls to Secret by Query = 1
4 Correct 374 ms 6052 KB Output is correct - number of calls to Secret by Init = 7499, maximum number of calls to Secret by Query = 1
5 Correct 370 ms 5972 KB Output is correct - number of calls to Secret by Init = 7512, maximum number of calls to Secret by Query = 1
6 Correct 372 ms 6132 KB Output is correct - number of calls to Secret by Init = 7513, maximum number of calls to Secret by Query = 1
7 Correct 368 ms 6048 KB Output is correct - number of calls to Secret by Init = 7509, maximum number of calls to Secret by Query = 1
8 Correct 376 ms 6544 KB Output is correct - number of calls to Secret by Init = 7512, maximum number of calls to Secret by Query = 1
9 Correct 371 ms 6224 KB Output is correct - number of calls to Secret by Init = 7511, maximum number of calls to Secret by Query = 1
10 Correct 378 ms 6220 KB Output is correct - number of calls to Secret by Init = 7511, maximum number of calls to Secret by Query = 1