Submission #775845

#TimeUsernameProblemLanguageResultExecution timeMemory
775845SanguineChameleonRadio Towers (IOI22_towers)C++17
18 / 100
766 ms1996 KiB
#include "towers.h" #include <bits/stdc++.h> using namespace std; const int maxN = 1e5 + 20; bool sub1; int cnt_min[maxN]; int H[maxN]; int N; int max_id; void init(int _N, vector<int> _H) { N = _N; for (int i = 0; i < N; i++) { H[i] = _H[i]; } max_id = 0; for (int i = 0; i < N; i++) { if (H[i] > H[max_id]) { max_id = i; } } sub1 = true; for (int i = 0; i < max_id; i++) { sub1 &= H[i] < H[i + 1]; } for (int i = max_id; i + 1 < N; i++) { sub1 &= H[i] > H[i + 1]; } for (int i = 1; i < N - 1; i++) { cnt_min[i] = cnt_min[i - 1] + (H[i] < H[i - 1] && H[i] < H[i + 1]); } } int max_towers(int L, int R, int D) { if (L == R) { return 1; } if (sub1) { if (R <= max_id) { return 1; } else if (L >= max_id) { return 1; } else { return 1 + (H[max_id] >= max(H[L], H[R]) + D); } } if (D == 1) { return cnt_min[R - 1] - cnt_min[L] + (H[L] < H[L + 1]) + (H[R] < H[R - 1]); } return 0; }
#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...