Submission #1077520

#TimeUsernameProblemLanguageResultExecution timeMemory
1077520pccRadio Towers (IOI22_towers)C++17
11 / 100
4074 ms7688 KiB
#include "towers.h" #include <vector> #include <bits/stdc++.h> #define pii pair<int,int> #define fs first #define sc second using namespace std; const int B = 20; const int mxn = 1e5+10; const int inf = 1e9; int N; vector<int> H; int par[mxn][B]; pii tree[mxn]; int arr[mxn]; int rt; int dep[mxn]; pii big[mxn]; pii eul[mxn]; int dp[mxn]; multiset<int> st[mxn]; void dfs(int now){ for(int i = 1;i<B;i++)par[now][i] = par[par[now][i-1]][i-1]; eul[now] = pii(now,now); if(tree[now].fs){ int nxt = tree[now].fs; assert(arr[now]>arr[nxt]); dep[nxt] = dep[now]+1; par[nxt][0] = now; dfs(nxt); eul[now].fs = eul[nxt].fs; } if(tree[now].sc){ int nxt = tree[now].sc; assert(arr[now]>arr[nxt]); dep[nxt] = dep[now]+1; par[nxt][0] = now; dfs(nxt); eul[now].sc = eul[nxt].sc; } return; } void add(int now,int tar,int val,int D){ int pos = now; for(int i = B-1;i>=0;i--){ int p = par[now][i]; if(arr[p]<tar)now = p; } if(arr[now]<tar)now = par[now][0]; if(arr[now]<tar)return; int side = 0; int rs = tree[now].sc; if(rs&&eul[rs].fs<=pos&&eul[rs].sc>=pos)side = 1; if(!side)big[now].fs = max(big[now].fs,val); else big[now].sc = max(big[now].sc,val); return; } int dfs1(int now,int D){ st[now].clear(); big[now].fs = big[now].sc = 0; dp[now] = 1; if(!tree[now].fs&&!tree[now].sc)st[now].insert(arr[now]); if(tree[now].fs){ int nxt = tree[now].fs; dfs1(nxt,D); dp[now] = max({dp[now],(int)st[nxt].size(),dp[nxt]}); while(!st[nxt].empty()&&*st[nxt].rbegin()+D)st[nxt].erase(st[nxt].find(*st[nxt].rbegin())); if(st[now].size()<st[nxt].size())st[now].swap(st[nxt]); for(auto &i:st[nxt])st[now].insert(i); } if(tree[now].sc){ int nxt = tree[now].fs; dfs1(nxt,D); dp[now] = max({dp[now],(int)st[nxt].size(),dp[nxt]}); while(!st[nxt].empty()&&*st[nxt].rbegin()+D<arr[now])st[nxt].erase(st[nxt].find(*st[nxt].rbegin())); if(st[now].size()<st[nxt].size())st[now].swap(st[nxt]); for(auto &i:st[nxt])st[now].insert(i); } cerr<<now<<":";for(auto &j:st[now])cerr<<j<<',';cerr<<endl; dp[now] = max(dp[now],(int)st[now].size()); return dp[now]; } void build(int s,int e){ for(auto &i:tree)i = pii(0,0); vector<int> st; for(int i = s;i<=e;i++){ while(!st.empty()&&arr[st.back()]<arr[i]){ tree[i].fs = st.back(); st.pop_back(); } if(!st.empty())tree[st.back()].sc = i; st.push_back(i); } rt = st[0]; par[rt][0] = rt; dfs(rt); } void init(int NN, std::vector<int> HH) { N = NN; arr[0] = inf; for(int i = 0;i<N;i++)arr[i+1] = HH[i]; } int max_towers(int L, int R, int D) { L++,R++; vector<pii> v; for(int i = L;i<=R;i++){ pii rng = pii(i,i); for(int j = i-1;j>=1;j--){ if(arr[j]>=arr[i]+D)break; rng.fs = j; } for(int j = i+1;j<=N;j++){ if(arr[j]>=arr[i]+D)break; rng.sc = j; } v.push_back(rng); } sort(v.rbegin(),v.rend()); int lp = N+1; int ans = 0; for(auto &[l,r]:v){ if(r<lp)ans++,lp = l; } return ans; }
#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...