• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Zadanie Licznik Długu XXVIII OI

Object Storage Arubacloud
0 głosów
536 wizyt
pytanie zadane 1 maja 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Mam problem z takim zadaniem: https://szkopul.edu.pl/problemset/problem/w3anjkOGa2eMEBt_-GYEosat/site/?key=statement

Napisałem bruta na 30pkt, że za każdym razem jak mam query, to robie dodawanie pisemne. O(N*Q), nie wiem jak to przyśpieszyć.

Z góry dzięki za pomoc i poświęcony czas!
komentarz 1 maja 2023 przez Whistleroosh Maniak (56,980 p.)
To jest całkiem proste zadanie. Pomyśl nad nim jeszcze troszke
komentarz 1 maja 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
A to nie będzie tak, żę tych przeskoczeń dużo razy będzie stosunkowo mało i wystarczy podreperować bruta pisemnego?
komentarz 1 maja 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
a jednak nie, tak by było, gdyby wszystkie updaty dawały cyfrę większą niż była poprzednio, a tak to mniejsze mogą psuć.
komentarz 1 maja 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Mam pomysł, który wydaje mi się, że krąży wokół dobrego rozwiązania. Na każdej pozycji trzymam sumę dwóch liczb na danej pozycji. I teraz jak dostaję zapytanie o liczbę na danej pozycji to jedyne co mnie interesuje, to to czy od wcześniejszego dostanę +1 czy nie, i teraz tak: jeśli suma wcześniejszego >= 10, to napewno dostanę, gdy <= 8 to nie dostanę, pytanie co gdy jest równa 9, wtedy może okazać się, że dostanie jeden od poprzedniego itd, więc niestety to jest dalej kwadratowe, ale to już ma potencjał jakby mogło działać. Jest to wmiarę dobry pomysł?
komentarz 1 maja 2023 przez Whistleroosh Maniak (56,980 p.)
Tak to idzie w dobrą stronę
komentarz 1 maja 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
a tu nie wejdzie drzewo przedziałowe punkt-przedział? bo wydaje mi się, że mam pomysł
komentarz 1 maja 2023 przez Whistleroosh Maniak (56,980 p.)
Może
komentarz 1 maja 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Mój pomysł jest taki: jeśli suma na pozycji i jest >= 10, to A[i] = 1, jak == 9, to A[i] = 0, jak <= 8 to A[i] = -1, dostaję zapytanie o pozycję x. Szukam gdzie jest pierwsza -1 na przedziale [x+1,n] i jeśli na przedziale [x+1,idx_pierwszej_minus_jedynki-1] robię querry, czy jest chociaż jedna 1. Jak jest to wiem, że dodaję jeden, jak nie to wiem, że nie dodaję. O(N lg N + Q lg N)?
komentarz 1 maja 2023 przez Whistleroosh Maniak (56,980 p.)
Może zadziała. Ja korzystałem tylko z 0 i 1 w drzewie.

1 odpowiedź

0 głosów
odpowiedź 1 maja 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
edycja 1 maja 2023 przez pasjonat_algorytmiki

Przeszło na 100pkt ten pomysł opisany w komentarzu. 

Kod dający 100pkt:

#include <iostream>
#include <vector>

using namespace std;

int n = 0, z = 0, base = (1 << 17), rozmiar_drzewa = base * 2, INF = 1e9;
string wewnetrzny;
string zewnetrzny;
char decyzja;
vector<int> stat_wewnetrzny;
vector<int> stat_zewnetrzny;
vector<int> drzewo_przedzialowe_minus_jeden;
vector<int> drzewo_przedzialowe_max;

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

inline int query_minus_jeden(int l, int p)
{
    l = l + base - 1, p = p + base + 1;
    int res = INF;
    while(l / 2 != p / 2)
    {
        if (l % 2 == 0)
            res = min(res,drzewo_przedzialowe_minus_jeden[l+1]);
        if (p % 2 == 1)
            res = min(res, drzewo_przedzialowe_minus_jeden[p-1]);
        l /= 2;
        p /= 2;
    }
    return res;
}

inline 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;
    }
}

inline int query_max(int l, int p)
{
    l = l + base - 1, p = p + base + 1;
    int res = -INF;
    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;
}


inline void napelniaj()
{
    stat_wewnetrzny.assign(n,0);
    stat_zewnetrzny.assign(n,0);
    for (int i = 1; i < n; ++i)
        stat_wewnetrzny[i] = (int)wewnetrzny[i-1]-48;
    for (int i = 1; i < n; ++i)
        stat_zewnetrzny[i] = (int)zewnetrzny[i-1]-48;

    drzewo_przedzialowe_max.assign(rozmiar_drzewa,-INF);
    drzewo_przedzialowe_minus_jeden.assign(rozmiar_drzewa,INF);
    for (int i = 1; i < n; ++i)
    {
        if (stat_wewnetrzny[i] + stat_zewnetrzny[i] <= 8)
            update_minus_jeden(i,i);
        else
            update_max(i,stat_wewnetrzny[i] + stat_zewnetrzny[i]);
    }
}

inline void update()
{
    int v = 0, val = 0;
    cin >> v >> val;
    v = n - v;

    if (stat_wewnetrzny[v] + stat_zewnetrzny[v] <= 8)
        update_minus_jeden(v,INF);
    else
        update_max(v,-INF);

    if (decyzja == 'W')
        stat_wewnetrzny[v] = val;
    else
        stat_zewnetrzny[v] = val;

    if (stat_wewnetrzny[v] + stat_zewnetrzny[v] <= 8)
            update_minus_jeden(v,v);
    else
        update_max(v,stat_wewnetrzny[v] + stat_zewnetrzny[v]);
}

inline int query()
{
    int v = 0, val = 0, idx_minus_jeden = 0, koniec_query = 0;
    cin >> v;
    v = n - v;

    val = stat_zewnetrzny[v] + stat_wewnetrzny[v];
    idx_minus_jeden = query_minus_jeden(v+1,n);

    if (idx_minus_jeden == INF)
        koniec_query = n;
    else
        koniec_query = idx_minus_jeden - 1;
    if (idx_minus_jeden == v+1)
        return val % 10;
    if (query_max(v+1,koniec_query) >= 10)
        return (val+1) % 10;
    return val % 10;
}

int main()
{
    /* Jeśli suma na pozycji i jest >= 10, to A[i] = 1,
       jak == 9, to A[i] = 0, jak <= 8 to A[i] = -1,
       dostaję zapytanie o pozycję x.
       Szukam gdzie jest pierwsza -1 na przedziale [x+1,n] i jeśli na przedziale [x+1,idx_pierwszej_minus_jedynki-1] robię querry,
       czy jest chociaż jedna 1. Jak jest to wiem, że dodaję jeden, jak nie to wiem, że nie dodaję. O(N lg N + Q lg N).
    */
    // https://forum.pasja-informatyki.pl/584364/zadanie-licznik-dlugu-xxviii-oi
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> z >> wewnetrzny >> zewnetrzny;

    napelniaj();

    while(z--)
    {
        cin >> decyzja;
        if (decyzja == 'S')
            cout << query() << '\n';
        else
            update();
    }

    return 0;
}

Dzięki za pomoc i dyskusję!

komentarz 1 maja 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
tak btw. to bardzo fajny ten pomysł, super zadanko
1
komentarz 1 maja 2023 przez Whistleroosh Maniak (56,980 p.)

Dla porównania kod, który korzysta tylko z 0 i 1 w drzewie:

#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

typedef uint32_t ul;
typedef int32_t l;
typedef uint64_t ull;
typedef int64_t ll;

const l INF = 1000000000 + 9;
const ll MOD = 123456789;
const l PRIME = 200003;
const ll L_INF = 1000000000000000000LL + 7;
const double EPS = 1e-5;

#define FOR(x, y, z) for (l z = x; z < y; z++)
#define FORE(x, y, z) for (l z = x; z <= y; z++)
#define FORD(x, y, z) for (l z = x; z > y; z--)
#define FORDE(x, y, z) for (l z = x; z >= y; z--)
#define REP(x, y) for (l y = 0; y < x; y++)
#define ALL(...) (__VA_ARGS__).begin(), (__VA_ARGS__).end()

#define PF push_front
#define POF pop_front
#define PB push_back
#define POB pop_back
#define MP make_pair
#define FS first
#define SC second

const l MAXN = 100005;
const l power = 1 << 19;
const l shift = 1 << 18;

l n, z;
l cnt_tree[power], node_size[power]; //cnt_tree -> cnt number of position of sum equal to 9
l inner[MAXN], outer[MAXN];

string debt;

void build()
{
    FORDE(n+shift, 1, i)
    {
        node_size[i/2] += node_size[i];
        cnt_tree[i/2] += cnt_tree[i];
    }
}

void update(l pos)
{
    cnt_tree[pos+shift] = (inner[pos]+outer[pos] == 9);
    pos += shift; pos >>= 1;

    while(pos)
    {
        cnt_tree[pos] = cnt_tree[2*pos]+cnt_tree[2*pos+1];
        pos >>= 1;
    }
}

bool check(l pos)
{
    pos += shift;

    while(pos)
    {
        if(pos % 2 == 0 && cnt_tree[pos+1] != node_size[pos+1])
        {
            pos += 1;
            break;
        }

        pos >>= 1;
    }

    while(pos < shift)
    {
        if(cnt_tree[2*pos] != node_size[2*pos])
            pos *= 2;

        else pos = 2*pos+1;
    }

    pos -= shift;

    return ((inner[pos]+outer[pos]) > 9);
}

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

    cin >> n >> z;

    cin >> debt;
    REP(n-1, i)
    {
        inner[i+1] = debt[i]-'0';
        node_size[i+1+shift] = 1;
    }
    node_size[shift] = 1; // 0 + shift
    node_size[n+shift] = 1; // 0 + shift

    cin >> debt;
    REP(n-1, i)
    {
        outer[i+1] = debt[i]-'0';

        if(inner[i+1]+outer[i+1] == 9)
            cnt_tree[i+1+shift] = 1;
    }

    build();

    char a;
    l b, c;

    REP(z, i)
    {
        cin >> a;

        switch (a)
        {
        case 'W':
            cin >> b >> c;
            inner[n-b] = c; // n - 1 - (b - 1)
            update(n-b);

            break;

        case 'Z':
            cin >> b >> c;
            outer[n-b] = c;
            update(n-b);

            break;

        case 'S':
            cin >> b;
            cout << (inner[n-b]+outer[n-b]+check(n-b))%10 << "\n";

            break;
        }
    }
}

 

komentarz 1 maja 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
ale wsm wygląda dośc podobnie

Podobne pytania

0 głosów
1 odpowiedź 129 wizyt
0 głosów
1 odpowiedź 609 wizyt
pytanie zadane 1 maja 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

92,693 zapytań

141,606 odpowiedzi

320,105 komentarzy

62,051 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...