Зачем получать этот код с минимальным диапазоном запросов?
Я пытался решить очень простую проблему, которая просто включала реализацию Range Minimum Query. Ссылка на проблему
Но я превышаю срок. Пожалуйста, кто-нибудь поможет в отладке моего кода.
#include <bits/stdc++.h>
#define inf 1000000000000000000
using namespace std;
vector<long long> segTree(2000005 , 0);
void createTree(vector<long long> v);
void createTreeUtil(vector<long long> v , int s,int e , int pos);
void updateTree(int x , int value , int n);
void updateTreeUtil(int s , int e , int pos , int x , int value);
long long getMinUtil(int s , int e , int pos , int srange , int erange);
long long getMin(int s , int e , int n);
int main(){
int n,q;
cin >> n >> q;
vector<long long> v(n);
for(int i=0;i<n;++i) cin >> v[i];
//cout << "yes" << endl;
createTree(v);
/*cout << "seg tree is " ;
for(int i=0;i<segTree.size();++i) cout << segTree[i] << " ";
cout << endl;*/
//cout << "yes" << endl;
while(q--){
int x , y;
char c;
cin >> c >> x >> y;
if(c == 'u'){
--x;
updateTree(x , y , n);
}
else{
--x , --y;
cout << getMin(x , y , n) << endl;
}
}
return 0;
}
void createTree(vector<long long> v){
int l = v.size();
createTreeUtil(v , 0 , l-1 , 0);
}
void createTreeUtil(vector<long long> v , int s,int e , int pos){
if(s>e) return;
int left = 2*pos+1 , right = 2*pos+2;
if(s==e){
segTree[pos] = v[s];
return;
}
int mid = (s+e)/2;
createTreeUtil(v , s , mid , left);
createTreeUtil(v , mid+1 , e , right);
segTree[pos] = min(segTree[left] , segTree[right]);
}
void updateTree(int x , int value , int n){
updateTreeUtil(0 , n-1 , 0 , x , value);
}
void updateTreeUtil(int s , int e , int pos , int x , int value){
if(s == e){
if(s == x) segTree[s] = value;
return;
}
if(x<s || x>e) return;
int left = 2*pos+1 , right= 2*pos+2 , mid = (s+e)/2;
updateTreeUtil(s , mid , left , x , value);
updateTreeUtil(mid+1 , e , right , x , value);
segTree[pos] = min(segTree[left] , segTree[right]);
}
long long getMin(int s , int e , int n){
return getMinUtil(0 , n-1 , 0 , s , e);
}
long long getMinUtil(int s , int e , int pos , int srange , int erange){
int mid = (s+e)/2 , left = 2*pos+1 , right = 2*pos+2;
if(s > erange || e < srange) return inf;
if(s >= srange && e <= erange) return segTree[pos];
return min(getMinUtil(s , mid , left , srange , erange) , getMinUtil(mid+1 , e , right , srange , erange));
}
заранее спасибо
1 ответ
Превышен лимит времени, потому что C++ передает аргументы по значению.
Это означает, что каждый раз, когда вызывается метод createTreeUtil, он создает новую копию входного вектора с 100 000 элементов.
Попробуйте изменить:
void createTree(vector<long long> v);
void createTreeUtil(vector<long long> v , int s,int e , int pos);
использовать ссылки:
void createTree(vector<long long> &v);
void createTreeUtil(vector<long long> &v , int s,int e , int pos);
(Вам нужно будет изменить эти сигнатуры как вверху файла, где функции объявлены, так и где функции фактически определены.)