Здравствуйте, помогите, пожалуйста, с задачей А(wrong answer 7 тест). Подскажите в чем моя ошибка. Спасибо.
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <math.h>
#define PI 3.14159265
#define eps 1e-18
using namespace std;
vector <int> a;
int k=1;
int q(int l,int r)
{
if(l>r)return 1000000000;
if(l==r)return a[l];
int mini=1000000000;
if(l<r)
{
if((l)%2!=0){mini=min(mini,a[l]);l++;}
if((r)%2==0){mini=min(mini,a[r]);r--;};
if(l<r)mini=min(mini,q(l/2,r/2));
}
return mini;
}
int main()
{
freopen("stupid_rmq.in","r",stdin);
freopen("stupid_rmq.out","w",stdout);
int i,j,l,m,mini,n,p,r;
cin>>n;
while(k<n)k*=2;
a.resize(4*n+1);
a.assign(sizeof(a),1000000000);
for(i=k;i<k+n;i++)cin>>a[i];
for(i=k+n-1;i>=1;i--)
a[i/2]=min(a[i/2],a[i]);
cin>>m;
for(i=1;i<=m;i++)
{
cin>>l>>r;
if(l>r)swap(l,r);
cout<<q(l+k-1,r+k-1)<<endl;
}
return 0;
}
UPD: Вопрос снят. Спасибо всем.
Код не открывается. Выложите его например на pastebin.com
Тупая версия RMQ (считаем l и r, и в лоб выберем минимум на этом промежутке) зайдет в силу таких маленьких ограничений.
Спасибо. Но я хотел бы решить не в тупую. Представьте, что n и m <= 10^5.
а как именно не работает?
wrong answer 7 тест.
Возможно, вы имели ввиду: Помогите, пожалуйста, с задачей.
Ваша программа через несколько запросов начинает выдавать нули, пока еще не понял почему. Вот тест.
Спасибо. Не могли бы вы написать тест в комментариях, так как я нахожусь в учебном учреждении, где нельзя зайти на посторонние сайты, кроме сайтов предназначенных для спортивного программирования.
Я генерил его рандомно, боюсь не влезет.
44
32137 16289 31381 9142 16716 26830 20457 9828 20862 3771 31959 23738 11101 28094 28715 20195 30900 391 2984 6437 24575 9392 5453 10262 8144 20117 19927 1292 31089 25446 20615 18133 11979 19067 8229 31400 6022 16103 1349 6492 4466 3663 8649 23768
8
18 21
44 44
40 40
22 39
20 34
15 27
2 27
19 39
Спасибо.
Массив до конца не заполнялся числом 10^9. Спасибо вам за тест.