Zadanie podciągi arytmetyczne - obóz naukowy ilocamp

Question

Mam problem z takim zadaniem: https://szkopul.edu.pl/problemset/problem/o58fvuJW4HyYGvadjH-w0_jN/site/?key=statement

Napisałem bruta O(N^2), na 55pkt, że idę pętlą for od 0, do n-1, i zakładam, że ten element jest środkowy(j), i dla każdego elementu środkowego, idę 2 pętlą for, po idx-ach j+1, j+2, j+3... i zakładam, że on jest tym prawym, a ten lewy wyszukuję z statystyk, (znaczę, sobie wcześniej jakie odwiedziłem), przekształcając:

A_j - A_i = A_k - A_j => A_i = 2*A_j - A_k

Gdzie A_i, to element lewy, A_j to element środkowy, A_k to element prawy.

Kod:

#include <iostream>
#include <vector>

using namespace std;

int n = 0, wczytana_liczba = 0, wyn = 0;
vector<int> liczby;
int stat[200005] = {0};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    
    for (int i = 0; i < n; ++i)
    {
        cin >> wczytana_liczba;
        liczby.push_back(wczytana_liczba);
    }

    for (int j = 0; j < n; ++j)
    {
        for (int k = j+1; k < n; ++k)
            if (2 * liczby[j] - liczby[k] > 0)
                if (stat[2 * liczby[j] - liczby[k]] == 1)
                    wyn++;
        stat[liczby[j]]++;
    }

    cout << wyn << '\n';

    return 0;
}

Tylko to jest zawolne. Podejrzewam, że trzeba użyć jakiegoś drzewa przedziałowego lub czegoś takiego, ale nie mam pomysłu jak. Ma ktoś pomysł?

Z góry dziekuję za pomoc i poświęcony czas!

Answer 1

Tutaj znalazłem skany z omówieniem no i okazuje się, ze to naprawdę trudne zadanie. Trzeba było skorzystać z bin searcha + hashy + palindromów. Takie coś mogłoby się pojawić na finale albo jako najtrudniejsze na I etapie