oj.uz

Submission #931149

# Submission time Handle Problem Language Result Execution time Memory
931149 2024-02-21T10:09:40 Z parlimoos Secret (JOI14_secret) C++14
100 / 100
 368 ms 13140 KB 
//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#include "secret.h"
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<int , x>
#define endl '\n'

int n;
vector<int> a;
int zam[4001][2][1000] , zaminf[4001];

void buildZam(int l = 0 , int r = n - 1 , int i = 1){
    int c = (r + l) >> 1 , res = a[c];
    zaminf[i] = c , zam[i][0][c] = a[c];
    if(r == l) return;
    zam[i][1][c + 1] = a[c + 1];
    for(int j = c - 1 ; j >= l ; j--) res = Secret(a[j] , res) , zam[i][0][j] = res;
    res = a[c + 1] , zam[i][0][c + 1] = a[c + 1];
    for(int j = c + 2 ; j <= r ; j++) res = Secret(res , a[j]) , zam[i][1][j] = res;
    if(r > l + 1) buildZam(l , c - 1 , i << 1);
    buildZam(c + 1 , r , (i << 1) | 1);
}
int getZam(int l , int r , int i){
    if(l <= zaminf[i] and r >= zaminf[i]){
        if(r == zaminf[i]) return zam[i][0][l];
        return Secret(zam[i][0][l] , zam[i][1][r]);
    }
    if(r < zaminf[i]) return getZam(l , r , i << 1);
    return getZam(l , r , (i << 1) | 1);
}
void Init(int N , int A[]){
    n = N;
    for(int i = 0 ; i < n ; i++) a.pb(A[i]);
    buildZam();
}
int Query(int L , int R){
    return getZam(L , R , 1);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 8784 KB Output is correct - number of calls to Secret by Init = 3331, maximum number of calls to Secret by Query = 1
2 Correct 103 ms 10840 KB Output is correct - number of calls to Secret by Init = 3339, maximum number of calls to Secret by Query = 1
3 Correct 103 ms 12888 KB Output is correct - number of calls to Secret by Init = 3347, maximum number of calls to Secret by Query = 1
4 Correct 359 ms 12884 KB Output is correct - number of calls to Secret by Init = 7467, maximum number of calls to Secret by Query = 1
5 Correct 364 ms 12884 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
6 Correct 360 ms 12892 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
7 Correct 358 ms 12880 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
8 Correct 366 ms 12904 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
9 Correct 360 ms 12880 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
10 Correct 368 ms 13140 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1