Submission #482595

#TimeUsernameProblemLanguageResultExecution timeMemory
482595HazemGlobal Warming (CEOI18_glo)C++14
100 / 100
1804 ms69484 KiB
#include <bits/stdc++.h> #define LL long long using namespace std; const int N = 2e5+1; const LL MOD = 1e9+7; int a[N],dp[N][2],tree[N*4*3],b[N]; int n,k; map<int,int>mp; set<int>st; void update(int v,int tl,int tr,int pos,int val){ if(tl==tr){ tree[v] = val; return ; } int mid = (tl+tr)/2; if(pos<=mid)update(v*2,tl,mid,pos,val); else update(v*2+1,mid+1,tr,pos,val); tree[v] = max(tree[v*2],tree[v*2+1]); } int get(int v,int tl,int tr,int l,int r){ if(tl>r||tr<l) return 0; if(tl>=l&&tr<=r) return tree[v]; int mid = (tl+tr)/2; return max(get(v*2,tl,mid,l,r),get(v*2+1,mid+1,tr,l,r)); } void calc(){ for(int i=1;i<=n;i++){ dp[i][0] = get(1,1,3*n,1,b[i]-1)+1; if(get(1,1,3*n,b[i],b[i])<dp[i][0])update(1,1,3*n,b[i],dp[i][0]); } for(int i=1;i<=n;i++) update(1,1,3*n,b[i],0); for(int i=n;i>=1;i--){ dp[i][1] = get(1,1,3*n,b[i]+1,3*n)+1; if(get(1,1,3*n,b[i],b[i])<dp[i][1])update(1,1,3*n,b[i],dp[i][1]); } for(int i=1;i<=n;i++) update(1,1,3*n,b[i],0); } void op(int l,int r,int x){ for(int i=l;i<=r;i++) a[i] += x; } struct Vertex { int left, right; int sum = 0; Vertex *left_child = nullptr, *right_child = nullptr; Vertex(int lb, int rb) { left = lb; right = rb; } void extend() { if (!left_child && left + 1 < right) { int t = (left + right) / 2; left_child = new Vertex(left, t); right_child = new Vertex(t, right); } } void add(int k, int x) { extend(); sum = max(sum,x); if (left_child) { if (k < left_child->right) left_child->add(k, x); else right_child->add(k, x); } } int get_sum(int lq, int rq) { if (lq <= left && right <= rq) return sum; if (max(left, lq) >= min(right, rq)) return 0; extend(); return max(left_child->get_sum(lq, rq),right_child->get_sum(lq, rq)); } }; int main(){ scanf("%d%d",&n,&k); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); st.insert(a[i]); st.insert(max(0,a[i]-k+1)); st.insert(min((int)1e9,a[i]+k-1)); } int cnt = 1; for(auto x:st) mp[x] = cnt++; for(int i=1;i<=n;i++) b[i] = mp[a[i]]; calc(); int ans = 0; for(int i=n;i>=1;i--){ ans = max(ans,dp[i][0]+get(1,1,n*3,mp[max(0,a[i]-k+1)],mp[min(a[i]+k-1,(int)1e9)])); if(get(1,1,3*n,b[i],b[i])<dp[i][1]) update(1,1,3*n,b[i],dp[i][1]); } for(int i=1;i<=n;i++) update(1,1,3*n,b[i],0); for(int i=1;i<=n;i++){ ans = max(ans,dp[i][1]+get(1,1,3*n,mp[max(0,a[i]-k+1)],mp[min(a[i]+k-1,(int)1e9)])); if(get(1,1,3*n,b[i],b[i])<dp[i][0]) update(1,1,3*n,b[i],dp[i][0]); } printf("%d\n",ans); }

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:106:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |     scanf("%d%d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~
glo.cpp:109:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |         scanf("%d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~
#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...