# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
166521 | losmi247 | Secret (JOI14_secret) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "secret.h"
using namespace std;
typedef long long ll;
typedef pair <int,int> p;
const int N = 1005;
int n,a[N];
int x[N][N];
/*int Secret(int a,int b){
cout << a << " " << b << endl;
int r;
cin >> r;
return r;
}*/
int daj(int l,int r,int trl,int trr){
if(r-l <= 1){
return -1;
}
int mid = (l+r)/2;
if(l <= trl && trr <= r && trl <= mid && trr >= mid+1){
return mid;
}
int x = daj(l,mid,trl,trr);
if(x != -1){
return x;
}
return daj(mid+1,r,trl,trr);
}
void nesto(int l,int r){
int mid = l+(r-l)/2;
if(mid >= r || mid < l){
return;
}
x[mid][mid] = a[mid];
x[mid+1][mid+1] = a[mid+1];
for(int i = mid-1; i >= l; i--){
x[i][mid] = Secret(a[i],x[i+1][mid]);
}
for(int i = mid+2; i <= r; i++){
x[mid+1][i] = Secret(x[mid+1][i-1],a[i]);
}
nesto(l,mid);
nesto(mid+1,r);
}
int Query(int l,int r){
if(l == r){
return a[l];
}
if(l+1 == r){
return Secret(a[l],a[r]);
}
int pos = daj(1,n,l,r);
/*cout << "naso " << pos << endl;
cout << "to su " << x[l][pos] << " " << x[pos+1][r] << endl;*/
return Secret(x[l][pos],x[pos+1][r]);
}
void Init(int l,int d[]){
n = l;
for(int i = 1; i <= n; i++){
a[i] = d[i-1];
}
nesto(1,n);
/*cout << "eve " << endl;
for(int i = 1; i <= n; i++){
for(int j = i; j <= n; j++){
cout << i << " " << j << " " << x[i][j] << endl;
}
}
cout << endl;*/
}
int main(){
int a[4] = {1,2,3,4};
Init(4,a);
cout << Query(2,4) << endl;
cout << Query(1,3) << endl;
cout << Query(1,4) << endl;
}