ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1989. Подпалиндромы

TLE14 Пример теста?
Послано Biplan 31 окт 2013 23:50
Хотелось бы пример теста
#pragma comment(linker, "/STACK:16777216")

#include <iostream>
using namespace std;

char  str[100001];

bool isPalind(int start, int finish)
{
    int fin = finish-1;//(int)finish-48 - 1;
    bool answer = true;
    for (int k=start-1; k<fin; k++)
    {
        if (str[k] != str[fin])
        {
            return false;
        }
        fin--;
    }
    return true;
}



int main()
{
    char c1, c2;
    int pos=0, m, fin;
    cin >> str;
    scanf("%d\n", &m);
    for (int i=0; i<m; i++)
    {
        scanf("%*[^? ]%c%d ", &c1, &pos);
        if (c1 == ' ')
        {
            scanf("%c", &c2);
            str[pos-1] = c2;
        }
        if (c1 == '?')
        {
            scanf("%d", &fin);
            if(isPalind(pos, fin))
            {
                printf("Yes\n");
            }
            else
            {
                printf("No\n");
            }
        }
    }
    return 0;
}

Edited by author 01.11.2013 00:11
Re: TLE14 Пример теста?
Послано MrDindows 1 ноя 2013 05:47
Асимптотика же O(nm) у вас.
Пример теста: ааа..ааа (10^5 штук), и 10^5 запросов: ? 1 100000