# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1076669 | allin27x | Radio Towers (IOI22_towers) | C++17 | 4091 ms | 5704 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<int> h;
vector<int> lc,rc,a;
void init(signed N, std::vector<signed> H){
h.resize(N); for (int i = 0; i < N; i++) h[i] = H[i];
}
int dfs(int i, int d){
if (i==-1) return 0;
if (lc[i]==-1 && rc[i]==-1) return -a[i];
int lans = dfs(lc[i],d);
int rans = dfs(rc[i],d);
if (lans < 0 && a[i] - d >= a[lc[i]]) lans = 1;
if (rans < 0 && a[i] - d >= a[rc[i]]) rans = 1;
if (!lans) return rans; if (!rans) return lans;
if (lans < 0 && rans < 0) return max(lans,rans);
if (lans < 0) return rans;
if (rans < 0) return lans;
return lans + rans;
}
signed max_towers(signed l, signed r, signed d){
int sz = r-l+1;
a.assign(sz,0); for (int i=l; i<=r; i++) a[i-l] = h[i];
a.push_back(2e9);
stack<int> st; st.push(sz);
lc.assign(sz+1,-1); rc.assign(sz+1,-1);
for (int i=0; i<sz; i++){
int last = -1;
while (a[i] > a[st.top()]) {
last=st.top();
st.pop();
}
lc[i] = last;
rc[st.top()]=i;
st.push(i);
}
return dfs(sz,d);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |