Submission #1170253

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170253		userro1234324	Two Antennas (JOI19_antennas)	C++20	0 / 100	171 ms	19348 KiB

antennas

#include <bits/stdc++.h>
using namespace std;
int n, q;
int h[200001];
int a[200001];
int b[200001];
struct p {
    int pocz;
    int kon;
    int indeks;
};
p pytania[200000];
int odpowiedzi[200000];
int kolejny;
pair <int, pair<bool, int>> zmiana_stanu[400000];
bool posortuj(p a, p b) {
    return a.kon < b.kon;
}
void wczytaj() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d %d %d", &h[i], &a[i], &b[i]);
        zmiana_stanu[kolejny++] = {i + a[i], {0, i}};
        zmiana_stanu[kolejny++] = {i + b[i], {1, i}};
    }
    scanf("%d", &q);
    for (int i = 0; i < q; i++) {
        scanf("%d %d", &pytania[i].pocz, &pytania[i].kon);
        pytania[i].indeks = i;
    }
    sort(pytania, pytania + q, posortuj);
    sort(zmiana_stanu, zmiana_stanu + kolejny);
}
const int maxn = 524288;
const int baza = 262143;
const int maksymalna_wartosc = 1000000001;
int drzewo_lewe_minimum[maxn];
int drzewo_lewe_maksimum[maxn];
int drzewo_prawe_minimum[maxn];
int drzewo_prawe_maksimum[maxn];
int drzewo_lewy_minus_prawy[maxn];
int drzewo_prawy_minus_lewy[maxn];
bool drzewo_czy_nalezy_spuscic[maxn];
void przygotuj_drzewa() {
    for (int i = 1; i < maxn; i++) {
        drzewo_lewe_minimum[i] = maksymalna_wartosc;
        drzewo_lewe_maksimum[i] = -1;
        drzewo_prawe_minimum[i] = maksymalna_wartosc;
        drzewo_prawe_maksimum[i] = -1;
        drzewo_lewy_minus_prawy[i] = -1;
        drzewo_prawy_minus_lewy[i] = -1;
    }
}
void wlacz_lewa_wartosc_na_drzewach_min_max(int indeks) {
    indeks += baza;
    drzewo_lewe_minimum[indeks] = h[indeks - baza];
    drzewo_lewe_maksimum[indeks] = h[indeks - baza];
    indeks >>= 1;
    while (indeks) {
        drzewo_lewe_minimum[indeks] = min(drzewo_lewe_minimum[2 * indeks], drzewo_lewe_minimum[2 * indeks + 1]);
        drzewo_lewe_maksimum[indeks] = max(drzewo_lewe_maksimum[2 * indeks], drzewo_lewe_maksimum[2 * indeks + 1]);
        indeks >>= 1;
    }
}
void wylacz_lewa_wartosc_na_drzewach_min_max(int indeks) {
    indeks += baza;
    drzewo_lewe_minimum[indeks] = maksymalna_wartosc;
    drzewo_lewe_maksimum[indeks] = -1;
    indeks >>= 1;
    while (indeks) {
        drzewo_lewe_minimum[indeks] = min(drzewo_lewe_minimum[2 * indeks], drzewo_lewe_minimum[2 * indeks + 1]);
        drzewo_lewe_maksimum[indeks] = max(drzewo_lewe_maksimum[2 * indeks], drzewo_lewe_maksimum[2 * indeks + 1]);
        indeks >>= 1;
    }
}
void spusc_na_dol(int x) {
    int syn1 = 2 * x; int syn2 = syn1 + 1;
    drzewo_czy_nalezy_spuscic[syn1] = true;
    drzewo_czy_nalezy_spuscic[syn2] = true;
    drzewo_czy_nalezy_spuscic[x] = false;
    // syn1
    drzewo_prawe_maksimum[syn1] = max(drzewo_prawe_maksimum[syn1], drzewo_prawe_maksimum[x]);
    drzewo_prawe_minimum[syn1] = min(drzewo_prawe_minimum[syn1], drzewo_prawe_minimum[x]);
    drzewo_lewy_minus_prawy[syn1] = max(drzewo_lewy_minus_prawy[syn1], drzewo_lewe_maksimum[syn1] - drzewo_prawe_minimum[syn1]);
    drzewo_prawy_minus_lewy[syn1] = max(drzewo_prawy_minus_lewy[syn1], drzewo_prawe_maksimum[syn1] - drzewo_lewe_minimum[syn1]);
    // to samo dla syn2
    drzewo_prawe_maksimum[syn2] = max(drzewo_prawe_maksimum[syn2], drzewo_prawe_maksimum[x]);
    drzewo_prawe_minimum[syn2] = min(drzewo_prawe_minimum[syn2], drzewo_prawe_minimum[x]);
    drzewo_lewy_minus_prawy[syn2] = max(drzewo_lewy_minus_prawy[syn2], drzewo_lewe_maksimum[syn2] - drzewo_prawe_minimum[syn2]);
    drzewo_prawy_minus_lewy[syn2] = max(drzewo_prawy_minus_lewy[syn2], drzewo_prawe_maksimum[syn2] - drzewo_lewe_minimum[syn2]);
}
int szukany_pocz, szukany_kon, wartosc;
int wynik_na_przedziale(int x, int aktualny_pocz, int aktualny_kon) {
    if (aktualny_pocz > szukany_kon || aktualny_kon < szukany_pocz) return -1;
    if (aktualny_pocz >= szukany_pocz && aktualny_kon <= szukany_kon) return max(drzewo_lewy_minus_prawy[x], drzewo_prawy_minus_lewy[x]);
    if (drzewo_czy_nalezy_spuscic[x]) spusc_na_dol(x);
    int syn1 = 2 * x; int syn2 = syn1 + 1;
    int wynik1 = wynik_na_przedziale(syn1, aktualny_pocz, (aktualny_pocz + aktualny_kon) / 2);
    int wynik2 = wynik_na_przedziale(syn2, (aktualny_pocz + aktualny_kon) / 2 + 1, aktualny_kon);
    return max(wynik1, wynik2);
}
void dodaj_wartosc_na_przedziale(int x, int aktualny_pocz, int aktualny_kon) {
    if (aktualny_pocz > szukany_kon || szukany_pocz > aktualny_kon) return;
    if (aktualny_pocz >= szukany_pocz && aktualny_kon <= szukany_kon) {
        drzewo_prawe_maksimum[x] = max(drzewo_prawe_maksimum[x], wartosc);
        drzewo_prawe_minimum[x] = min(drzewo_prawe_minimum[x], wartosc);
        drzewo_lewy_minus_prawy[x] = max(drzewo_lewy_minus_prawy[x], drzewo_lewe_maksimum[x] - drzewo_prawe_minimum[x]);
        drzewo_prawy_minus_lewy[x] = max(drzewo_prawy_minus_lewy[x], drzewo_prawe_maksimum[x] - drzewo_lewe_minimum[x]);
        drzewo_czy_nalezy_spuscic[x] = true;
        return;
    }
    if (drzewo_czy_nalezy_spuscic[x]) spusc_na_dol(x);
    dodaj_wartosc_na_przedziale(2 * x, aktualny_pocz, (aktualny_pocz + aktualny_kon) / 2);
    dodaj_wartosc_na_przedziale(2 * x + 1, (aktualny_pocz + aktualny_kon) / 2 + 1, aktualny_kon);
    drzewo_prawe_maksimum[x] = min(drzewo_prawe_maksimum[2 * x], drzewo_prawe_maksimum[2 * x + 1]);
    drzewo_prawe_minimum[x] = max(drzewo_prawe_minimum[2 * x], drzewo_prawe_minimum[2 * x + 1]);
    drzewo_lewy_minus_prawy[x] = max(drzewo_lewy_minus_prawy[2 * x], drzewo_lewy_minus_prawy[2 * x + 1]);
    drzewo_prawy_minus_lewy[x] = max(drzewo_prawy_minus_lewy[2 * x], drzewo_prawy_minus_lewy[2 * x + 1]);
}
void pospuszczaj_sie_do_indeksu(int indeks) {
    int x = 1, pocz = 1, kon = baza + 1;
    while (x != indeks + baza) {
        spusc_na_dol(x);
        int srodek = (pocz + kon) / 2;
        if (indeks <= srodek) {
            x = 2 * x;
            kon = srodek;
        }
        else {
            x = 2 * x + 1;
            pocz = srodek + 1;
        }
    }
}
void wlacz_indeks(int indeks) {
    wlacz_lewa_wartosc_na_drzewach_min_max(indeks);
    pospuszczaj_sie_do_indeksu(indeks);
    indeks += baza;
    drzewo_prawe_maksimum[indeks] = -1;
    drzewo_prawe_minimum[indeks] = maksymalna_wartosc;
    indeks >>= 1;
    while (indeks) {
        drzewo_prawe_maksimum[indeks] = -1;
        drzewo_prawe_minimum[indeks] = maksymalna_wartosc;
        indeks >>= 1;
    }
}
void wylacz_indeks(int indeks) {
    wylacz_lewa_wartosc_na_drzewach_min_max(indeks);
    //pospuszczaj_sie_do_indeksu(indeks);
    //indeks += baza;
    //drzewo_prawe_maksimum[indeks] = -1;
    //drzewo_prawe_minimum[indeks] = maksymalna_wartosc;
    //indeks >>= 1;
    //while (indeks) {
        //drzewo_prawe_maksimum[indeks] = -1;
        //drzewo_prawe_minimum[indeks] = maksymalna_wartosc;
        //indeks >>= 1;
    //}
}
void zrob_zadanie() {
    int l = 0;
    int s = 0;
    for (int i = 1; i <= n; i++) {
        while (l < kolejny && zmiana_stanu[l].first == i && zmiana_stanu[l].second.first == 0) {
            wlacz_indeks(zmiana_stanu[l].second.second);
            l++;
        }
        szukany_pocz = max(i - b[i], 1);
        szukany_kon = i - a[i];
        if (szukany_pocz <= szukany_kon) {
            wartosc = h[i];
            dodaj_wartosc_na_przedziale(1, 1, baza + 1);
        }
        while (s < q && pytania[s].kon == i) {
            szukany_pocz = pytania[s].pocz;
            szukany_kon = pytania[s].kon;
            odpowiedzi[pytania[s].indeks] = wynik_na_przedziale(1, 1, baza + 1);
            s++;
        }
        while (l < kolejny && zmiana_stanu[l].first == i && zmiana_stanu[l].second.first == 1) {
            wylacz_indeks(zmiana_stanu[l].second.second);
            l++;
        }
    }
}
void wypisz_odpowiedzi() {
    for (int i = 0; i < q; i++) {
        printf("%d\n", odpowiedzi[i]);
    }
}
int main() {
    wczytaj();
    przygotuj_drzewa();
    zrob_zadanie();
    wypisz_odpowiedzi();
}

Compilation message (stderr)

antennas.cpp: In function 'void wczytaj()':
antennas.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
antennas.cpp:22:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         scanf("%d %d %d", &h[i], &a[i], &b[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
antennas.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         scanf("%d %d", &pytania[i].pocz, &pytania[i].kon);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 2
• Subtask 2: 0 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 65