Submission #68509

#TimeUsernameProblemLanguageResultExecution timeMemory
68509losmi247Secret (JOI14_secret)C++14
0 / 100
673 ms9016 KiB
#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; srand(time(0)); for(int i = 0; i < N; i++){ //update(0,n-1,i,A[i],0); a[i] = A[i]; } for(int i = 0; i < n; i++){ int k = i+rand()%(n-i-1); get(0,n-1,i,k,0); } build(0,n-1,0); cin >> Q; while(Q--){ cin >> l >> r; cout << Query(l,r) << endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...