# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
68498 | losmi247 | Secret (JOI14_secret) | C++14 | 804 ms | 5540 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;
int Q,l,r;
int drvo[2000005];
int n,a[2000005];
typedef pair <int,int> p;
map <p,int> mapa;
int secret(int x,int y){
if(mapa.count(p(x,y))){
return mapa[p(x,y)];
}
return mapa[p(x,y)] = Secret(x,y);
}
void update(int i,int j,int poz,int val,int node){
if(i == j){
drvo[node] = val;
return;
}
int mid = i+(j-i)/2;
if(poz <= mid){
update(i,mid,poz,val,2*node+1);
}
else{
update(mid+1,j,poz,val,2*node+2);
}
drvo[node] = secret(drvo[2*node+1],drvo[2*node+2]);
}
void build(int i,int j,int node){
if(i == j){
drvo[node] = a[i];
return;
}
int mid = i+(j-i)/2;
build(i,mid,2*node+1);
build(mid+1,j,2*node+2);
drvo[node] = secret(drvo[2*node+1],drvo[2*node+2]);
}
int get(int i,int j,int l,int r,int node){
if(j < l || i > r){
return -1;
}
if(l <= i && r >= j){
return drvo[node];
}
int mid = i+(j-i)/2;
int p1 = get(i,mid,l,r,2*node+1),p2=get(mid+1,j,l,r,2*node+2);
if(p1 == -1){
return p2;
}
else if(p2 == -1){
return p1;
}
else{
return secret(get(i,mid,l,r,2*node+1),get(mid+1,j,l,r,2*node+2));
}
}
int Query(int L,int R){
return get(0,n-1,L,R,0);
}
void Init(int N,int A[]){
n = N;
for(int i = 0; i < N; i++){
//update(0,n-1,i,A[i],0);
a[i] = A[i];
}
build(0,n-1,0);
cin >> Q;
while(Q--){
cin >> l >> r;
cout << Query(l,r) << endl;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |