oj.uz

Submission #703303

# Submission time Handle Problem Language Result Execution time Memory
703303 2023-02-26T22:36:16 Z bane Secret (JOI14_secret) C++17
100 / 100
 447 ms 4580 KB 
#include <bits/stdc++.h>
#include "secret.h"
using namespace std;
typedef long long ll;
const int MAX = 10005;

ll arr[MAX], ret[40][MAX], mask[MAX];
int n;
void init(int l, int r, int lvl = 0){
	if (l == r) {
        ret[lvl][l] = arr[l];
        return;
    }
    int m = (l + r) >> 1;
    ret[lvl][m] = arr[m];
    for (int i = m - 1; i >= l; i--) ret[lvl][i] = Secret(arr[i], ret[lvl][i + 1]);
    ret[lvl][m + 1] = arr[m + 1];
    for (int i = m + 2; i <= r; i++) ret[lvl][i] = Secret(ret[lvl][i - 1], arr[i]);
    init(l, m, lvl+1);
    init(m + 1, r, lvl+1);
}
int get(int l, int r, int lvl, int L, int R){
	if (l == r)return ret[lvl][l];
	int m = (l + r) / 2;
	if (R<=m)return get(l,m,lvl+1,L,R);
	else if (L > m)return get(m+1,r,lvl+1,L,R);
	else return Secret(ret[lvl][L], ret[lvl][R]);
}
void Init(int N_, int A[]) {
	n = N_;
	for (int i = 0; i  < n; ++i)arr[i] = A[i];
	
	init(0,n-1,0);
}

int Query(int L, int R) {
	return get(0,n-1,0,L,R);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 2444 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 124 ms 2472 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 2432 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 447 ms 4356 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 430 ms 4580 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 4404 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 437 ms 4416 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 426 ms 4412 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 447 ms 4336 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 4348 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1