Submission #1076744

#TimeUsernameProblemLanguageResultExecution timeMemory
1076744vjudge1Radio Towers (IOI22_towers)C++17
23 / 100
4091 ms80772 KiB
#include "towers.h" #include <bits/stdc++.h> using namespace std; using vi = vector<int>; const int INF = 1e9; int n; vi H; vi St, Dr; vi DeltaSt, DeltaDr; struct RMQ { int n; vector<vi> A; RMQ(vi V0) : n((int)V0.size()) { A.push_back(V0); for(int k = 1; (1 << k) <= n; ++k) { A.push_back(A.back()); for(int i = 0; i < n; ++i) { if(i + (1 << (k - 1)) < n) A[k][i] = max(A[k][i], A[k - 1][i + (1 << (k - 1))]); } } } int query(int l, int r) { int d = 31 - __builtin_clz(r - l + 1); return max(A[d][l], A[d][r - (1 << d) + 1]); } }; pair<vi, vi> descomp(vi A) { RMQ R(A); vi Ant(n, -1); vi Delta(n, INF); /// cel mai mare delta posibil stack<int> S; for(int i = 0; i < n; ++i) { while(!S.empty() && A[S.top()] > A[i]) { S.pop(); } if(!S.empty()) { Ant[i] = S.top(); Delta[i] = R.query(S.top(), i) - A[i]; } S.push(i); } return make_pair(Ant, Delta); } vi S; const int MN = 100000; struct AIB2D { int n; vi V[4 * MN]; AIB2D() {} AIB2D(const vi &V0) : n((int)V0.size()) { build(V0, 1, 0, n - 1); } void build(const vi &V0, int u, int s, int d) { for(int i = s; i <= d; ++i) V[u].push_back(V0[i]); sort(V[u].begin(), V[u].end()); if(s != d) { build(V0, u << 1, s, (s + d) >> 1); build(V0, u << 1 | 1, ((s + d) >> 1) + 1, d); } } int query(int l, int r, int D, int u, int s, int d) { if(d < l || r < s) return 0; if(l <= s && d <= r) { int v = lower_bound(V[u].begin(), V[u].end(), D) - V[u].begin(); return int(V[u].size()) - v; } return query(l, r, D, u << 1, s, (s + d) >> 1) + query(l, r, D, u << 1 | 1, ((s + d) >> 1) + 1, d); } int query(int l, int r, int D) { return query(l, r, D, 1, 0, n - 1); } }; AIB2D ASt, ADr; AIB2D ATot; void init(int N0, vi H0) { n = N0; H = H0; tie(St, DeltaSt) = descomp(H); reverse(H.begin(), H.end()); tie(Dr, DeltaDr) = descomp(H); reverse(H.begin(), H.end()); reverse(Dr.begin(), Dr.end()); reverse(DeltaDr.begin(), DeltaDr.end()); for(auto &it : Dr) it = n - it - 1; S.resize(n); for(int i = 0; i < n; ++i) S[i] = min(DeltaSt[i], DeltaDr[i]); ASt = AIB2D(DeltaSt); ADr = AIB2D(DeltaDr); ATot = AIB2D(S); } int max_towers(int l, int r, int D) { vi Sol; for(int i = l; i <= r; ++i) { if(S[i] >= D) { Sol.push_back(i); } } if(ATot.query(l, r, D) == 0) { ///poate gasim un SolDr >= D si dupa un SolSt >= D int st = l, dr = r, mij; if(ADr.query(l, r, D) == 0) return 1; while(st < dr) { mij = (st + dr) / 2; if(ADr.query(l, r, D)) dr = mij; else st = mij + 1; } if(ASt.query(st + 1, r, D)) return 2; return 1; } int st, dr, mij; int p1; st = l, dr = r; while(st < dr) { mij = (st + dr) / 2; if(ATot.query(l, mij, D)) dr = mij; else st = mij + 1; } p1 = st; int p2; st = l; dr = r; while(st < dr) { mij = (st + dr + 1) / 2; if(ATot.query(mij, r, D)) st = mij; else dr = mij - 1; } p2 = st; int found_st = 0, found_dr = 0; found_st = !!ADr.query(l, p1 - 1, D); found_dr = !!ASt.query(p2 + 1, r, D); return int(Sol.size()) + found_st + found_dr; }
#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...