oj.uz

Submission #916452

# Submission time Handle Problem Language Result Execution time Memory
916452 2024-01-26T00:54:57 Z biank Secret (JOI14_secret) C++14
100 / 100
 388 ms 4608 KB 
#include <bits/stdc++.h>
#include "secret.h"
using namespace std;
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define forn(i,n) for(int i=0;i<int(n);i++)
#define dforsn(i,s,n) for(int i=int(n)-1;i>=int(s);i--)
#define dforn(i,n) for(int i=int(n)-1;i>=0;i--)

const int MAXN = 1000;
const int MAXL = 10;

int val[MAXL][MAXN];
int n;

void build(int l, int r, int a[], int h) {
    int m = (l+r)/2;
    val[h][m] = a[m];
    if(l==r) return;
    //prefix
    val[h][m+1] = a[m+1];
    forsn(i,m+2,r+1) {
        val[h][i] = Secret(val[h][i-1], a[i]);
    }
    //suffix
    dforsn(i,l,m) {
        val[h][i] = Secret(a[i], val[h][i+1]);
    }
    build(l,m,a,h+1);
    build(m+1,r,a,h+1);
}

void Init(int N, int a[]) {
    n=N;
    build(0,n-1,a,0);
}

int solve(int l, int r, int a, int b, int h) {
    if(l==r) return val[h][a];
    int m=(l+r)/2;
    if(b<=m) return solve(l,m,a,b,h+1);
    if(a>=m+1) return solve(m+1,r,a,b,h+1);
    return Secret(val[h][a], val[h][b]);
}

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

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 2648 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 115 ms 2728 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 110 ms 2664 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 384 ms 4408 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 386 ms 4440 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 381 ms 4268 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 380 ms 4232 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 388 ms 4608 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 385 ms 4432 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 385 ms 4432 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1