Submission #931140

#	Time	Username	Problem	Language	Result	Execution time	Memory
931140		parlimoos	Secret (JOI14_secret)	C++14	0 / 100	374 ms	12908 KiB

secret

//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];
        if(l == zaminf[i]) return zam[i][1][r];
        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: 0 / 100