Zadanie Promocja finał OI, optymalizacja pamięci - set

Question

Mam problem z optymalizacją tego zadania z finału 7 OI-a: https://szkopul.edu.pl/problemset/problem/VD_bKhKPiYjm8uq-R8O1r88h/site/?key=statement

Kod jest bardzo prosty. Oprócz wczytania danych jest dokładnie 5 linii.

#include <iostream>
#include <set>

using namespace std;
typedef long long ll;

int n = 0, k = 0, wczytana_liczba = 0;
ll wyn = 0;
multiset<int> S;

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

    cin >> n;
    while(n--)
    {
        cin >> k;
        while(k--)
        {
            cin >> wczytana_liczba;
            S.insert(wczytana_liczba);
        }
        wyn += *S.rbegin() - *S.begin();
        S.erase(S.lower_bound(*S.begin()));
        S.erase(S.lower_bound(*S.rbegin()));
    }
    printf("%lld",wyn);
    return 0;
}

Przechodzi tylko na 80pkt, wywala się pamięć. Pewnie trzeba dobrać jakąś lepszą strukturę danych, ma ktoś jakiś pomysł?

Z góry dziękuję za pomoc i poświęcony czas.

Comments

wywala się pamięć.

Co to znaczy? Jakiś błąd wykonania, czy po prostu program przekracza limit?

---

dostępna pamięc na zadanie to 32MB, a program przekracza limit.

---

Próbowałeś użyć wektora?

---

No tak wsumie, sobie myślę, że na rozwiązanie tego w dobrej pamięci są 2 opcje:

1 - To co ja zrobiłem z drzewami przedziałowymi punkt-przedział min i max. O(n log n)

2 - Zaimplementować kopiec binarny i też by przeszło w O(n log n).

Set z tego co wyczytałem to jest bardzo pamieciożerny. To zadanie jest z finału OI-a a jest bardzo proste.

I kopiec by działał jak max_val > 10^6, a to działa tylko dlatego, bo max val <= 10^6

Answer 1

Przeszło już na 100pkt w O(n log n), korzystając z tego, że max val <= 10^6 zrobiłem drzewo przedziałowe minów i drzewo przedziałowe maxów i pamięć jest liniowa, bo drzewo przedziałowe to vector. Kod

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
typedef long long ll;

int n = 0, k = 0, wczytana_liczba = 0, base = 0, rozmiar_drzewa = 0, min_zap = 0, max_zap = 0;
ll wyn = 0;
vector<int> ile(1e6+1,0);
vector<int> drzewo_przedzialowe_max;
vector<int> drzewo_przedzialowe_min;

void update_min(int v, int val)
{
    v += base;
    drzewo_przedzialowe_min[v] = val;
    v /= 2;
    while (v > 0)
    {
        drzewo_przedzialowe_min[v] = min(drzewo_przedzialowe_min[v * 2], drzewo_przedzialowe_min[v * 2 + 1]);
        v /= 2;
    }
}

void update_max(int v, int val)
{
    v += base;
    drzewo_przedzialowe_max[v] = val;
    v /= 2;
    while (v > 0)
    {
        drzewo_przedzialowe_max[v] = max(drzewo_przedzialowe_max[v * 2], drzewo_przedzialowe_max[v * 2 + 1]);
        v /= 2;
    }
}

int querry_min(int l, int p)
{
    l = l + base - 1;
    p = p + base + 1;
    int res = 1e6+5;
    while(l / 2 != p / 2)
    {
        if (l % 2 == 0)
            res = min(res,drzewo_przedzialowe_min[l+1]);
        if (p % 2 == 1)
            res = min(res, drzewo_przedzialowe_min[p-1]);
        l /= 2;
        p /= 2;
    }
    return res;
}

int querry_max(int l, int p)
{
    l = l + base - 1;
    p = p + base + 1;
    int res = -1e6+5;
    while(l / 2 != p / 2)
    {
        if (l % 2 == 0)
            res = max(res,drzewo_przedzialowe_max[l+1]);
        if (p % 2 == 1)
            res = max(res, drzewo_przedzialowe_max[p-1]);
        l /= 2;
        p /= 2;
    }
    return res;
}

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

    base = (1 << ((int)ceil((double)log2(1e6+1))));
    rozmiar_drzewa = base * 2;
    drzewo_przedzialowe_min.assign(rozmiar_drzewa,1e6+5);
    drzewo_przedzialowe_max.assign(rozmiar_drzewa,0);

    cin >> n;
    while(n--)
    {
        cin >> k;
        while(k--)
        {
            cin >> wczytana_liczba;
            ile[wczytana_liczba]++;
            update_min(wczytana_liczba,wczytana_liczba);
            update_max(wczytana_liczba,wczytana_liczba);
        }
        max_zap = querry_max(1,1e6);
        //cout << "MAX ZAP: " << max_zap << endl;
        ile[max_zap]--;
        if (ile[max_zap] == 0)
        {
            update_max(max_zap,0);
            update_min(max_zap,1e6+5);
        }
        min_zap = querry_min(1,1e6);
        ile[min_zap]--;
        if (ile[min_zap] == 0)
        {
            update_max(min_zap,0);
            update_min(min_zap,1e6+5);
        }
        wyn += max_zap - min_zap;
        //cout << "Wyn:" << wyn << endl;
    }
    printf("%lld",wyn);
    return 0;
}

 

Comments

Można też zwykłą mapą zrobić

---

A mapa ma mniejszą pamięc niż set?

---

Powinna mieć mniej więcej taką samą pamięć. Ale przynajmniej redukuje duplikaty i może to pomogło

---

Mapa też wchodzi na 100(pamięc spoko), z czasami praktycznie takimisamymi jak drzewo przedziałowe. W niektórych testach minimalnie gorzej, w niektórych minimalnie lepiej. Wniosek taki, że gdy nie trzeba robić żadnego find-a albo coś takiego, to lepiej użyć mapy.

Zauważyłem, że na OI-u mają taki bardzo dziwny zwyczaj, że jak nie zależy na pamięci to dają np 1GB, 512MB, 256MB, 128MB albo coś takiego, a jak zależy to dają np 64MB, 32MB itp. xD

---

@Whistleroosh, 

Ale przynajmniej redukuje duplikaty i może to pomogło

A std::set nie?

---

Racja, mówiłem to w odniesieniu do multiseta użytego w zadaniu.

---

@pasjonat_algorytmiki, 

btw, bardzo podobne zadanie na drzewo punkt-przedział po wartościach: 

https://sio2.mimuw.edu.pl/c/zwo21/p/naj-cpp/

Bardzo polecam.