Submission #626839

#TimeUsernameProblemLanguageResultExecution timeMemory
626839dnialhRadio Towers (IOI22_towers)C++17
0 / 100
4065 ms15108 KiB
#include <vector> #include <map> #include <set> #include <iostream> #define map std::map #define set std::set #define vector std::vector #define vi vector<int> #define ll long long #define pb push_back #define vll vector<ll> int fd = -1; int n; vi heights; vector<vi> steppers; void init(int N, vector<int> H){ n = N; heights = H; } void compute(int d){ vi nhi(n + 1, n); int best = -1; int vb = -1; int last = n; for (int i = n - 1; i >= 0; i--){ int v = heights[i]; if (v > vb){ best = i; vb = v; } if (vb >= v + d){ last = best; best = -1; vb = -1; for (int j = i; j < last; j++){ if (heights[j] >= heights[i] + d){ last = j; break; } } } nhi[i] = last; //std::cout << "nhi " << i << " " << last << std::endl; } vi nlo(n + 1, n); ll lbest = -1; ll lvb = -1; int llast = n; for (int i = n - 1; i >= 0; i--){ ll v = 15e8 - heights[i]; if (v > lvb){ lbest = i; lvb = v; } if (lvb >= v + d){ llast = lbest; lbest = -1; lvb = -1; for (int j = i; j < llast; j++){ if (heights[i] >= heights[j] + d){ llast = j; break; } } } nlo[i] = llast; } steppers = vector<vi>(); vi first; for (int i = 0; i <= n; i++){ first.pb(nlo[nhi[i]]); } steppers.pb(first); for (int j = 0; j < 30; j++){ vi nex; vi curr = steppers[j]; for (int i = 0; i <= n; i++){ nex.pb(curr[curr[i]]); } steppers.pb(nex); } //std::cout << steppers.size() << std::endl; } int max_towers(int L, int R, int D){ if (D != fd){ compute(D); fd = D; } int out = 1; int curr = L; for (int j = 29; j >= 0; j--){ //std::cout << j << " " << out << " " << curr << std::endl; int att = steppers[j][curr]; if (att <= R){ out += (1 << j); curr = att; } } return out; } /* 7 3 10 20 60 40 50 30 70 1 5 10 2 2 100 0 6 17 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...