제출 #1074826

#제출 시각아이디문제언어결과실행 시간메모리
1074826dostsGlobal Warming (CEOI18_glo)C++17
100 / 100
419 ms110784 KiB
//Dost SEFEROĞLU #include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define ff first #define ss second #define sp << " " << #define all(cont) cont.begin(),cont.end() #define vi vector<int> const int MOD = 1e9+7,inf = 2e12; const int N = 5001; vi vv; int idx(int x) { return upper_bound(all(vv),x)-vv.begin(); } struct FT{ int n; vi bit; FT(int nn) { n = nn; bit.assign(nn+1,0); } void put(int p,int v) { for (int i=p;i<=n;i+=i&-i) bit[i]=max(bit[i],v); } int get(int p) { int ans = 0; for (int i=p;i>0;i-=i&-i) ans=max(ans,bit[i]); return ans; } void reset() { bit.assign(n+1,0); } }; struct ST { vector<multiset<int,greater<int>>> t; vector<int> ans; ST(int nn) { t.resize(4*nn+1); ans.resize(4*nn+1); } void insert(int node,int l,int r,int p,int v) { if (l == r) { t[node].insert(v); ans[node] = *t[node].begin(); return; } int m = (l+r) >> 1; if (p<=m) insert(2*node,l,m,p,v); else insert(2*node+1,m+1,r,p,v); ans[node] = max(ans[2*node],ans[2*node+1]); } void erase(int node,int l,int r,int p,int v) { if (l == r) { t[node].erase(t[node].find(v)); if (t[node].empty()) ans[node] = 0; else ans[node] = *t[node].begin(); return; } int m = (l+r) >> 1; if (p<=m) erase(2*node,l,m,p,v); else erase(2*node+1,m+1,r,p,v); ans[node] = max(ans[2*node],ans[2*node+1]); } int query(int node,int l,int r,int L,int R) { if (l > R || r < L) return 0; if (l >= L && r<=R) return ans[node]; int m = (l+r) >> 1; return max(query(2*node,l,m,L,R),query(2*node+1,m+1,r,L,R)); } }; void solve() { int n,x; cin >> n >> x; //corollary: always decrease some prefix //corollary: if you decrease 1..i you MUST use i. vi a(n+1); for (int i=1;i<=n;i++) cin >> a[i]; for (int i=1;i<=n;i++) { vv.push_back(a[i]); vv.push_back(a[i]-x); } sort(all(vv)); vv.erase(unique(all(vv)),vv.end()); int sz = vv.size(); FT ft(sz); vi p(n+1),s(n+1); for (int i=1;i<=n;i++) { p[i] = ft.get(idx(a[i])-1)+1; ft.put(idx(a[i]),p[i]); } ft.reset(); for (int i=n;i>=1;i--) { s[i] = ft.get(sz-idx(a[i]))+1; ft.put(sz-idx(a[i])+1,s[i]); } ft.reset(); int ans = 0; ST st(sz); for (int i=1;i<=n;i++) st.insert(1,1,sz,idx(a[i]),s[i]); for (int i=1;i<=n;i++) { st.erase(1,1,sz,idx(a[i]),s[i]); ans = max(ans,p[i]+st.query(1,1,sz,idx(a[i]-x)+1,sz)); } cout << ans << endl; } signed main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #ifdef Dodi freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif int t = 1; //cin >> t; while (t --> 0) solve(); }
#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...