Блог пользователя visionary

Автор visionary, 12 лет назад, По-русски

Здравствуйте, помогите, пожалуйста, с задачей А(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: Вопрос снят. Спасибо всем.

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Код не открывается. Выложите его например на pastebin.com

»
12 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Тупая версия RMQ (считаем l и r, и в лоб выберем минимум на этом промежутке) зайдет в силу таких маленьких ограничений.

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Спасибо. Но я хотел бы решить не в тупую. Представьте, что n и m <= 10^5.

»
12 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

а как именно не работает?

»
12 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

Возможно, вы имели ввиду: Помогите, пожалуйста, с задачей.

»
12 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Ваша программа через несколько запросов начинает выдавать нули, пока еще не понял почему. Вот тест.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Спасибо. Не могли бы вы написать тест в комментариях, так как я нахожусь в учебном учреждении, где нельзя зайти на посторонние сайты, кроме сайтов предназначенных для спортивного программирования.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Я генерил его рандомно, боюсь не влезет.

    • »
      »
      »
      12 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Массив до конца не заполнялся числом 10^9. Спасибо вам за тест.