Submission #1187341

#TimeUsernameProblemLanguageResultExecution timeMemory
1187341thelegendary08Financial Report (JOI21_financial)C++17
19 / 100
171 ms37936 KiB
#include<bits/stdc++.h> #define pb push_back #define mp make_pair #define int long long #define vi vector<int> #define vvi vector<vector<int>> #define pii pair<int, int> #define vpii vector<pair<int, int>> #define vc vector<char> #define vb vector<bool> #define mii map<int,int> #define f0r(i,n) for(int i=0;i<n;i++) #define FOR(i,k,n) for(int i=k;i<n;i++) #define all(v) (v).begin(),(v).end() #define rall(v) (v).rbegin(),(v).rend() #define in(a) int a; cin>>a #define in2(a,b) int a,b; cin>>a>>b #define in3(a,b,c) int a,b,c; cin>>a>>b>>c #define in4(a,b,c,d) int a,b,c,d; cin>>a>>b>>c>>d #define vin(v,n); vi v(n); f0r(i,n){cin>>v[i];} #define out(a) cout<<a<<'\n' #define out2(a,b) cout<<a<<' '<<b<<'\n' #define out3(a,b,c) cout<<a<<' '<<b<<' '<<c<<'\n' #define out4(a,b,c,d) cout<<a<<' '<<b<<' '<<c<<' '<<d<<'\n' #define pout(a) cout<<a.first<<' '<<a.second<<'\n' #define vout(v) for(auto u : v){cout<<u<<' ';} cout<<'\n' #define dout(a) cout<<a<<' '<<#a<<'\n' #define dout2(a,b) cout<<a<<' '<<#a<<' '<<b<<' '<<#b<<'\n' #define yn(x); if(x){cout<<"YES"<<'\n';}else{cout<<"NO"<<'\n';} const int leg = 1e9 + 7; const int mod = 998244353; using namespace std; struct minsegtree{ int n; vi tree; void update(int k, int x){ k += n; tree[k] = x; for(k/=2; k>=1; k/=2){ tree[k] = min(tree[k*2], tree[k*2+1]); } } int quer(int l, int r){ l += n; r += n; int ret = 4e18; while(l <= r){ if(l % 2 == 1)ret = min(ret, tree[l++]); if(r % 2 == 0)ret = min(ret, tree[r--]); l/=2; r/=2; } return ret; } minsegtree(vi &a){ n = a.size(); tree.resize(2*n+5); f0r(i,n)update(i,a[i]); } }; struct maxsegtree{ int n; vi tree; void build(int node, int l, int r, vi &a){ if(l == r){ tree[node] = a[l]; return; } int mid = (l + r) / 2; build(node*2, l, mid, a); build(node*2+1, mid+1, r, a); tree[node] = max(tree[node*2], tree[node*2+1]); } int firsthigher(int node, int tl, int tr, int l, int r, int x){ if(tl > r || tr < l) return -1; if(tree[node] <= x) return -1; if (tl== tr) return tl; int tm = tl + (tr-tl)/2; int left = firsthigher(2*node, tl, tm, l, r, x); if(left != -1) return left; return firsthigher(2*node+1, tm+1, tr, l ,r, x); } void update(int node, int tl, int tr, int k, int x){ if(tl == tr){ tree[node] = x; return; } int tm = (tl + tr) / 2; if(tm >= k){ update(node*2, tl, tm, k, x); } else{ update(node*2+1, tm+1, tr, k, x); } tree[node] = max(tree[node*2], tree[node*2+1]); } int quer(int node, int tl, int tr, int l, int r){ if(tl == l && tr == r)return tree[node]; if(tl > r || tr < l)return 0; int tm = (tl + tr) / 2; return max(quer(node*2, tl, tm, l, min(r, tm)), quer(node*2+1, tm+1, tr, max(l, tm+1), r)); } maxsegtree(vi &a){ n = a.size(); tree.resize(4*n+5); build(1, 0, n-1, a); } }; signed main(){ ios::sync_with_stdio(false); cin.tie(NULL); //ifstream cin(".in"); //ofstream cout(".out"); in2(n,d); vin(v,n); minsegtree t = minsegtree(v); vi m(n); FOR(i, d, n){ m[i] = t.quer(i-d, i); } // vout(m); maxsegtree u = maxsegtree(m); vi r(n); f0r(i,n){ r[i] = u.firsthigher(1, 0, n-1, i+d, n-1, v[i]); } f0r(i,n){ if(r[i] == -1)r[i] = n; } // vout(r); vpii q; f0r(i,n){ q.pb(mp(v[i], -i)); } sort(rall(q)); vi dp(n,-4e18); maxsegtree tt = maxsegtree(dp); f0r(i,n){ int dex = -q[i].second; int ne = max(0LL, tt.quer(1, 0, n-1, dex+1, r[dex]-1)) + 1; dp[dex] = ne; // dout2(dex, ne); tt.update(1, 0, n-1, dex, ne); } out(*max_element(all(dp))); }
#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...