Submission #1020315

#TimeUsernameProblemLanguageResultExecution timeMemory
1020315kymRadio Towers (IOI22_towers)C++17
23 / 100
4025 ms5072 KiB
#include "towers.h" #include <bits/stdc++.h> using namespace std; const int MAXN = 100005; vector<int>A; int n; struct node { int tree[4*MAXN]; void build(int node, int s, int e){ tree[node]=0; if(s!=e){ int m=(s+e)/2; build(node<<1,s,m); build(node<<1|1,m+1,e); } } void update(int node, int s, int e, int x, int nval){ if(s==e){ tree[node]=nval; return; } int m=(s+e)/2; if(x<=m)update(node<<1,s,m,x,nval); else update(node<<1|1,m+1,e,x,nval); tree[node]=max(tree[node<<1],tree[node<<1|1]); } int query(int node, int s, int e, int x, int y){ if(s==x&&e==y)return tree[node]; int m=(s+e)/2; if(y<=m)return query(node<<1,s,m,x,y); else if(x>m)return query(node<<1|1,m+1,e,x,y); else return max(query(node<<1,s,m,x,m),query(node<<1|1,m+1,e,m+1,y)); } int walk(int node, int s, int e, int tar){ if(s==e)return s; int m=(s+e)/2; if(tree[node<<1|1]>=tar)return walk(node<<1|1,m+1,e,tar); else return walk(node<<1,s,m,tar); } }seg,sa; int ls[MAXN]; void init(int N, std::vector<int> H) { n=N; A=H; } typedef pair<int,int>pi; int max_towers(int L, int R, int D) { sa.build(1,0,n); seg.build(1,0,n); int dp[n+5];memset(dp,0,sizeof dp); for(int i=0;i<n;i++)dp[i]=1; int ans=1; priority_queue<pi,vector<pi>,greater<pi>>pq; for(int i=L;i<=R;i++){ int lf=sa.walk(1,0,n,A[i]+D); if(L<=lf-1){ int mx=seg.query(1,0,n,L,lf-1); dp[i]=max(dp[i],mx+1); ans=max(ans,dp[i]); } while(pq.size() && pq.top().first <= A[i]-D){ pi cur=pq.top();pq.pop(); //cerr<<cur.second<<" "<<dp[cur.second]<<"\n"; seg.update(1,0,n,cur.second,dp[cur.second]); } sa.update(1,0,n,i,A[i]); pq.push({A[i],i}); } 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...