oj.uz

Submission #533035

# Submission time Handle Problem Language Result Execution time Memory
533035 2022-03-04T14:29:02 Z Lobo Secret (JOI14_secret) C++17
100 / 100
 510 ms 4876 KB 
#include<bits/stdc++.h>
#include "secret.h"
using namespace std;

const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

#define maxn 1010

int n, a[maxn], pf[maxn][30], sf[maxn][30];

void dc(int l, int r, int lv) {
    int mid = (l+r)/2;
    // cout << lv << " " << l << " " << r << " " << mid << endl;

    pf[mid+1][lv] = a[mid+1];
    for(int i = mid+2; i <= r; i++) {
        pf[i][lv] = Secret(pf[i-1][lv],a[i]);
    }


    sf[mid][lv] = a[mid];
    for(int i = mid-1; i >= l; i--) {
        sf[i][lv] = Secret(a[i],sf[i+1][lv]);
    }
    for(int i = mid; i >= l; i--) {
        // cout << " " << i << " " << sf[i][lv] << endl;
    }


    if(l != r) {
        dc(l,mid,lv+1);
        dc(mid+1,r,lv+1);
    }
}

int qrr(int l, int r, int lv, int L, int R) {
    int mid = (l+r)/2;
    // cout << l << " " << r << " --" << lv << " " << mid << " " << L << " " << R << endl;
    if(L >= mid+1) {
        return qrr(mid+1,r,lv+1,L,R);
    }
    else if(R <= mid) {
        return qrr(l,mid,lv+1,L,R);
    }
    else {
        return Secret(sf[L][lv],pf[R][lv]);
    }
}

int32_t Query(int32_t L, int32_t R) {
    if(L == R) return a[L];
    return qrr(0,n-1,0,L,R);
}

void Init(int32_t N, int32_t A[]) {
    n = N;
    for(int i = 0; i < n; i++) a[i] = A[i];

    dc(0,n-1,0);
}

// int32_t main() {
//     ios::sync_with_stdio(false); cin.tie(0);

//     // freopen("in.in", "r", stdin);
//     //freopen("out.out", "w", stdout);

//     int32_t N;
//     cin >> N;
//     int32_t A[N];
//     for(int i = 0; i < N; i++) cin >> A[i];

//     Init(N,A);

//     int q; cin >> q;
//     while(q--) {
//         int l,r; cin >> l >> r;

//         cout << Query(l,r) << endl;
//     }

// }

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 2700 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 134 ms 2616 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 133 ms 2628 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 463 ms 4776 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 484 ms 4792 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 456 ms 4876 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 482 ms 4732 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 455 ms 4804 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 451 ms 4752 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 4824 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1