Submission #775870

#TimeUsernameProblemLanguageResultExecution timeMemory
775870SanguineChameleonRadio Towers (IOI22_towers)C++17
41 / 100
4091 ms13736 KiB
#include "towers.h" #include <bits/stdc++.h> using namespace std; const int maxN = 1e5 + 20; bool sub1; vector<int> events[maxN]; int firstL[maxN]; int firstR[maxN]; int dp[maxN]; int bit[maxN]; 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]); } } void update(int pos, int val) { for (int i = pos; i <= N; i += i & (-i)) { bit[i] = max(bit[i], val); } } int get(int pos) { int res = 0; for (int i = pos; i > 0; i -= i & (-i)) { res = max(res, bit[i]); } return res; } 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]); } for (int i = L; i <= R; i++) { firstL[i] = L - 1; firstR[i] = R + 1; for (int j = i; j <= R; j++) { if (H[j] >= H[i] + D) { firstR[i] = j; break; } } for (int j = i; j >= L; j--) { if (H[j] >= H[i] + D) { firstL[i] = j; break; } } if (firstR[i] < R) { events[firstR[i] + 1].push_back(i); } } int res = 0; for (int i = L; i <= R; i++) { for (auto id: events[i]) { update(id + 1, dp[id]); } dp[i] = 1 + (firstL[i] > L ? get(firstL[i]) : 0); res = max(res, dp[i]); } return res; }
#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...