Zadanie Licznik Długu XXVIII OI

Question

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!

Comments

To jest całkiem proste zadanie. Pomyśl nad nim jeszcze troszke

---

A to nie będzie tak, żę tych przeskoczeń dużo razy będzie stosunkowo mało i wystarczy podreperować bruta pisemnego?

---

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ć.

---

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ł?

---

Tak to idzie w dobrą stronę

---

a tu nie wejdzie drzewo przedziałowe punkt-przedział? bo wydaje mi się, że mam pomysł

---

Może

---

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)?

---

Może zadziała. Ja korzystałem tylko z 0 i 1 w drzewie.

Answer 1

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ę!

Comments

tak btw. to bardzo fajny ten pomysł, super zadanko

---

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

 

---

ale wsm wygląda dośc podobnie