#include <cstdio> #include <vector> #include <algorithm> #ifdef DBG const bool dbg = true; #else const bool dbg = false; #endif using namespace std; const int MAX_N = 500000; typedef unsigned long long ull; struct Drzewo { int szyb_wzrostu; int ilosc_takich, ilosc_wiekszych; ull wysokosc_sciecia; ull ostatnie_ciecie; ull suma_wiekszych; Drzewo *lsyn; Drzewo *psyn; }; void wypiszDrzewo(Drzewo * d) { if (!dbg) return; printf("(%d, %d, %d, %llu, %llu, %llu, %s, %s)\n", d->szyb_wzrostu, d->ilosc_takich, d->ilosc_wiekszych, d->wysokosc_sciecia, d->ostatnie_ciecie, d->suma_wiekszych, d->lsyn ? "JEST" : "NIE MA", d->psyn ? "JEST" : "NIE MA"); } void wypiszDrzewoRek(Drzewo * d) { if (!dbg) return; wypiszDrzewo(d); if (d->lsyn) wypiszDrzewoRek(d->lsyn); if (d->psyn) wypiszDrzewoRek(d->psyn); } ull poprz_dzien = 0, dzien = 1, suma = 0, wys; int n, m; int a[MAX_N+1]; vector<Drzewo> szybkosci; Drzewo * wektorDoDrzewa(vector<Drzewo> w, int pocz, int kon) { if (pocz > kon) return NULL; int s = (pocz + kon) / 2; Drzewo *d = &w[s]; d->lsyn = wektorDoDrzewa(w, pocz, s - 1); d->psyn = wektorDoDrzewa(w, s + 1, kon); return d; } ull faktycznyKlucz(Drzewo * d, ull dzien) { return d->szyb_wzrostu * (dzien - d->ostatnie_ciecie) + d->wysokosc_sciecia; } Drzewo * znajdzPierwszeWieksze(Drzewo * d, ull dzien, ull wysokosc) { if (d == NULL) return NULL; if (faktycznyKlucz(d, dzien) > wysokosc) { Drzewo *inny = znajdzPierwszeWieksze(d->lsyn, dzien, wysokosc); d->ostatnie_ciecie = dzien; d->wysokosc_sciecia = wysokosc; return inny == NULL ? d : inny; } if (d->psyn != NULL && d->psyn->ostatnie_ciecie < d->ostatnie_ciecie) { d->psyn->ostatnie_ciecie = d->ostatnie_ciecie; d->psyn->wysokosc_sciecia = d->wysokosc_sciecia; } return znajdzPierwszeWieksze(d->psyn, dzien, wysokosc); } int main() { scanf("%d %d", &n, &m); int tmp_szybkosc; // zerujemy tablice for (int i = 1; i < n + 1; i++) { a[i] = 0; } // zliczamy ile czego jest for (int i = 0; i < n; i++) { scanf("%d", &tmp_szybkosc); if (dbg) printf("%d\n", tmp_szybkosc); a[tmp_szybkosc]++; } int j; // wrzucamy unikalne szybkosci do wektora for (int i = 1; i < n + 1; i++) { if (a[i] != 0) { szybkosci.push_back({ i, a[i], 0, 0, 0, 0, NULL, NULL }); if (dbg) printf("%d\n", szybkosci[szybkosci.size()-1].szyb_wzrostu); } } // sortujemy //sort(szybkosci.begin(), szybkosci.end(), [] (Drzewo a, Drzewo b) { return a.szyb_wzrostu < b.szyb_wzrostu; }); // sumy prefixowe (suma plonow i ilosci wyzszych) int kw = szybkosci.size() - 1; szybkosci[kw].suma_wiekszych = szybkosci[kw].szyb_wzrostu * szybkosci[kw].ilosc_takich; szybkosci[kw].ilosc_wiekszych = 0; for (int i = szybkosci.size() - 2; i >= 0; i--) { szybkosci[i].suma_wiekszych = szybkosci[i].szyb_wzrostu * szybkosci[i].ilosc_takich + szybkosci[i+1].suma_wiekszych; szybkosci[i].ilosc_wiekszych = szybkosci[i+1].ilosc_takich + szybkosci[i+1].ilosc_wiekszych; } if (dbg) { for (int d = 0; d < szybkosci.size(); d++) printf("(%d, %d, %d, %llu), ", szybkosci[d].szyb_wzrostu, szybkosci[d].ilosc_takich, szybkosci[d].ilosc_wiekszych, szybkosci[d].suma_wiekszych); printf("\n"); } // drzewo BST by szybciej wyszukiwac Drzewo * d = wektorDoDrzewa(szybkosci, 0, szybkosci.size() - 1); wypiszDrzewoRek(d); Drzewo * tmp; ull dzisiejsza_suma; for (int i = 0; i < m; i++) { scanf("%llu %llu", &dzien, &wys); tmp = znajdzPierwszeWieksze(d, dzien, wys); if (tmp == NULL) { printf("0\n"); } else { dzisiejsza_suma = (tmp->suma_wiekszych * dzien) - suma - (tmp->ilosc_wiekszych + 1) * wys; printf("%llu\n", dzisiejsza_suma); suma += dzisiejsza_suma; wypiszDrzewoRek(d); } } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 | #include <cstdio> #include <vector> #include <algorithm> #ifdef DBG const bool dbg = true; #else const bool dbg = false; #endif using namespace std; const int MAX_N = 500000; typedef unsigned long long ull; struct Drzewo { int szyb_wzrostu; int ilosc_takich, ilosc_wiekszych; ull wysokosc_sciecia; ull ostatnie_ciecie; ull suma_wiekszych; Drzewo *lsyn; Drzewo *psyn; }; void wypiszDrzewo(Drzewo * d) { if (!dbg) return; printf("(%d, %d, %d, %llu, %llu, %llu, %s, %s)\n", d->szyb_wzrostu, d->ilosc_takich, d->ilosc_wiekszych, d->wysokosc_sciecia, d->ostatnie_ciecie, d->suma_wiekszych, d->lsyn ? "JEST" : "NIE MA", d->psyn ? "JEST" : "NIE MA"); } void wypiszDrzewoRek(Drzewo * d) { if (!dbg) return; wypiszDrzewo(d); if (d->lsyn) wypiszDrzewoRek(d->lsyn); if (d->psyn) wypiszDrzewoRek(d->psyn); } ull poprz_dzien = 0, dzien = 1, suma = 0, wys; int n, m; int a[MAX_N+1]; vector<Drzewo> szybkosci; Drzewo * wektorDoDrzewa(vector<Drzewo> w, int pocz, int kon) { if (pocz > kon) return NULL; int s = (pocz + kon) / 2; Drzewo *d = &w[s]; d->lsyn = wektorDoDrzewa(w, pocz, s - 1); d->psyn = wektorDoDrzewa(w, s + 1, kon); return d; } ull faktycznyKlucz(Drzewo * d, ull dzien) { return d->szyb_wzrostu * (dzien - d->ostatnie_ciecie) + d->wysokosc_sciecia; } Drzewo * znajdzPierwszeWieksze(Drzewo * d, ull dzien, ull wysokosc) { if (d == NULL) return NULL; if (faktycznyKlucz(d, dzien) > wysokosc) { Drzewo *inny = znajdzPierwszeWieksze(d->lsyn, dzien, wysokosc); d->ostatnie_ciecie = dzien; d->wysokosc_sciecia = wysokosc; return inny == NULL ? d : inny; } if (d->psyn != NULL && d->psyn->ostatnie_ciecie < d->ostatnie_ciecie) { d->psyn->ostatnie_ciecie = d->ostatnie_ciecie; d->psyn->wysokosc_sciecia = d->wysokosc_sciecia; } return znajdzPierwszeWieksze(d->psyn, dzien, wysokosc); } int main() { scanf("%d %d", &n, &m); int tmp_szybkosc; // zerujemy tablice for (int i = 1; i < n + 1; i++) { a[i] = 0; } // zliczamy ile czego jest for (int i = 0; i < n; i++) { scanf("%d", &tmp_szybkosc); if (dbg) printf("%d\n", tmp_szybkosc); a[tmp_szybkosc]++; } int j; // wrzucamy unikalne szybkosci do wektora for (int i = 1; i < n + 1; i++) { if (a[i] != 0) { szybkosci.push_back({ i, a[i], 0, 0, 0, 0, NULL, NULL }); if (dbg) printf("%d\n", szybkosci[szybkosci.size()-1].szyb_wzrostu); } } // sortujemy //sort(szybkosci.begin(), szybkosci.end(), [] (Drzewo a, Drzewo b) { return a.szyb_wzrostu < b.szyb_wzrostu; }); // sumy prefixowe (suma plonow i ilosci wyzszych) int kw = szybkosci.size() - 1; szybkosci[kw].suma_wiekszych = szybkosci[kw].szyb_wzrostu * szybkosci[kw].ilosc_takich; szybkosci[kw].ilosc_wiekszych = 0; for (int i = szybkosci.size() - 2; i >= 0; i--) { szybkosci[i].suma_wiekszych = szybkosci[i].szyb_wzrostu * szybkosci[i].ilosc_takich + szybkosci[i+1].suma_wiekszych; szybkosci[i].ilosc_wiekszych = szybkosci[i+1].ilosc_takich + szybkosci[i+1].ilosc_wiekszych; } if (dbg) { for (int d = 0; d < szybkosci.size(); d++) printf("(%d, %d, %d, %llu), ", szybkosci[d].szyb_wzrostu, szybkosci[d].ilosc_takich, szybkosci[d].ilosc_wiekszych, szybkosci[d].suma_wiekszych); printf("\n"); } // drzewo BST by szybciej wyszukiwac Drzewo * d = wektorDoDrzewa(szybkosci, 0, szybkosci.size() - 1); wypiszDrzewoRek(d); Drzewo * tmp; ull dzisiejsza_suma; for (int i = 0; i < m; i++) { scanf("%llu %llu", &dzien, &wys); tmp = znajdzPierwszeWieksze(d, dzien, wys); if (tmp == NULL) { printf("0\n"); } else { dzisiejsza_suma = (tmp->suma_wiekszych * dzien) - suma - (tmp->ilosc_wiekszych + 1) * wys; printf("%llu\n", dzisiejsza_suma); suma += dzisiejsza_suma; wypiszDrzewoRek(d); } } } |