oj.uz

Submission #1015730

# Submission time Handle Problem Language Result Execution time Memory
1015730 2024-07-06T17:11:17 Z mnbvcxz123 Secret (JOI14_secret) C++17
100 / 100
 293 ms 4436 KB 
        #include<bits/stdc++.h>
        #include"secret.h"
        using namespace std;
        using ll=long long;
        using pi=pair<int,int>;
         
        #define pb push_back
        #define fi first
        #define se second
         
        constexpr int N=1e3+5;
        constexpr int lg=11;
        int res[lg][N];
        int mask[N];
        int a[N];
         
        void build(int l, int r, int pw){
                if(l==r)return;
                int m=(l+r)>>1;
                res[pw][m]=a[m];
                for(int i=m-1;i>=l;--i)
                        res[pw][i]=Secret(a[i],res[pw][i+1]);
                res[pw][m+1]=a[m+1];
                for(int i=m+2;i<=r;++i)
                        res[pw][i]=Secret(res[pw][i-1],a[i]);
                for(int i=m+1;i<=r;++i)
                        mask[i]^=1<<pw;
                build(l,m,pw+1);
                build(m+1,r,pw+1);
        }
         
        void Init(int n, int t[]){
                for(int i=0;i<n;++i)
                        a[i]=t[i];
                build(0,n-1,0);
        }
         
        int Query(int l, int r){
                if(l==r)return a[l];
                int x=__builtin_ctz(mask[l]^mask[r]);
                return Secret(res[x][l],res[x][r]);
        }

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 2460 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 82 ms 2500 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 86 ms 2560 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 290 ms 4332 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 275 ms 4436 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 293 ms 4356 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 276 ms 4436 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 278 ms 4436 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 270 ms 4320 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 281 ms 4432 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1