제출 #1081161

#제출 시각아이디문제언어결과실행 시간메모리
1081161abdelhakimFinancial Report (JOI21_financial)C++14
0 / 100
371 ms57700 KiB
#include <bits/stdc++.h> #define dbg(x) cout << #x <<' '<< x << endl; #define mod 1000000007LL #define inf 1e17 #define ll long long using namespace std; void printvec(vector<ll> vec) { for (auto &&e : vec) { cout << e << ' '; } cout << endl; } ll maxn = 300000+5; vector<ll> tree(4*maxn, inf); ll query(ll l, ll r, ll x, ll y, ll node) { if(max(l, x) > min(r, y)) { return inf; } if(x <= l && r <= y) { return tree[node]; } ll mid = (l+r)/2; return min(query(l, mid, x,y, node*2+1), query(mid+1, r, x, y, node*2+2)); } void update(ll l, ll r, ll pos, ll val, ll node) { if(pos > r || pos < l) return; if(l==r) { tree[node] = val; return; } ll mid = (l+r)/2; update(l, mid, pos, val, node*2+1); update(mid+1, r, pos, val, node*2+2); tree[node] = min(tree[node*2+1], tree[node*2+2]); } vector<ll> tree2(maxn*4); ll query2(ll l, ll r, ll x, ll y, ll node) { if(max(l, x) > min(r, y)) { return 0; } if(x <= l && r <= y) { return tree2[node]; } ll mid = (l+r)/2; return max(query2(l, mid, x,y, node*2+1), query2(mid+1, r, x, y, node*2+2)); } void update2(ll l, ll r, ll pos, ll val, ll node) { if(pos > r || pos < l) return; if(l==r) { tree2[node] = val; return; } ll mid = (l+r)/2; update2(l, mid, pos, val, node*2+1); update2(mid+1, r, pos, val, node*2+2); tree2[node] = max(tree2[node*2+1], tree2[node*2+2]); } int main() { ios::sync_with_stdio(false); cin.tie(0); int n, d; cin >> n >> d; vector<ll> a(n); for (int i = 0; i < n; i++) cin >> a[i]; vector<ll> temp = a; sort(temp.begin(),temp.end()); vector<ll> order(n); map<ll,ll> rnk; ll cur=0; for (int i = 0; i < n;i++) { if(i == 0 || temp[i]!=temp[i-1]) { cur++; } rnk[temp[i]] = cur; } for (int i = 0; i < n; i++) { order[i] = rnk[a[i]]; } ll l, r; l=r=0; deque<pair<ll,ll>> dq; for (int i = 0; i < d; i++) { while(!dq.empty() && dq.back().first >= order[i]) { dq.pop_back(); } dq.push_back({order[r], r}); r++; } map<ll,ll> minsi; minsi[r-1] = dq[0].first; while(r<n) { while(!dq.empty() && dq.back().first >= order[r]) { dq.pop_back(); } dq.push_back({order[r], r}); r++; if(l == dq[0].second) dq.pop_front(); l++; minsi[r-1] = dq[0].first; } vector<ll> R(n); for (int i=n-1;i>=0;i--) { R[i] = query(1, n, order[i]+1, n, 0); if(R[i] == inf) R[i] = n-1; if(minsi[i] != 0) { update(1, n, minsi[i], i,0); } } vector<ll> dp(n,1); vector<pair<ll,ll>> v(n); for (int i=0;i<n;i++) { v[i] = {order[i],i}; } sort(v.begin(), v.end(), greater<pair<ll,ll>>()); for (int i = 0; i < n; i++) { dp[v[i].second] += query2(0,n-1,i,R[i],0); update2(0,n-1,v[i].second,dp[v[i].second],0); } cout << *max_element(dp.begin(), dp.end()) << endl; }
#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...