Submission #1221399

#TimeUsernameProblemLanguageResultExecution timeMemory
1221399totoroRadio Towers (IOI22_towers)C++20
4 / 100
299 ms13472 KiB
#include <map> #include <vector> #include "towers.h" int n; std::vector<int> heights; std::vector<int> heightsc; std::vector<std::vector<int>> stc; std::map<int, int> cc; std::vector<int> invcc; void init(int N, std::vector<int> H) { n = N; for (int i : H) cc[i] = 0; int cccounter = 0; for (auto& [x, y] : cc) y = cccounter++, invcc.push_back(x); heightsc = heights = H; for (int& i : heightsc) i = cc[i]; stc.push_back(heightsc); for (int sz = 1; sz < 20; ++sz) { stc.emplace_back(); for (int i = 0; i + (1 << sz) <= N; ++i) { stc[sz].push_back(std::max(stc[sz - 1][i], stc[sz - 1][i + (1 << (sz - 1))])); } } } int rangemax(int l, int r) { int sz = r - l + 1; int log = -1; while (sz) sz >>= 1, ++log; return invcc[std::max(stc[log][l], stc[log][r - (1 << log) + 1])]; } bool can_communicate(int x, int y, int interference) { return rangemax(x, y) >= std::max(heights[x], heights[y]) + interference; } int max_towers(int l, int r, int d) { return 1 + (can_communicate(l, r, d)); }
#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...