Submission #1213760

#TimeUsernameProblemLanguageResultExecution timeMemory
1213760mychecksedadFinancial Report (JOI21_financial)C++17
100 / 100
406 ms15252 KiB
/* Author : Mychecksdead */ #include<bits/stdc++.h> using namespace std; #define ll long long int #define MOD (1000000000+7) #define MOD1 (998244353) #define pb push_back #define all(x) x.begin(), x.end() #define en cout << '\n' #define ff first #define ss second #define pii pair<int,int> #define vi vector<int> const int N = 2e6+100, M = 1e5+10, K = 52, MX = 30; int n, d, a[N], T[N], S[N], lazy[N]; void build(int l, int r, int k){ lazy[k] = 0; if(l == r){ T[k] = 0; S[k] = MOD; return; } int mid = l+r>>1; build(l, mid, k<<1); build(mid+1, r, k<<1|1); T[k] = 0; S[k] = MOD; } void push(int k){ S[k<<1] = max(S[k<<1], lazy[k]); S[k<<1|1] = max(S[k<<1|1], lazy[k]); lazy[k<<1|1] = max(lazy[k<<1|1], lazy[k]); lazy[k<<1] = max(lazy[k<<1], lazy[k]); lazy[k] = 0; } void upd(int l, int r, int p, int k, int val, int idx){ if(l == r){ if(val == 0) T[k] = val; else T[k] = max(T[k], val); S[k] = idx; return; } int mid = l+r>>1; push(k); if(p <= mid) upd(l, mid, p, k<<1, val, idx); else upd(mid+1, r, p, k<<1|1, val, idx); T[k] = max(T[k<<1], T[k<<1|1]); S[k] = min(S[k<<1], S[k<<1|1]); } void upd2(int l, int r, int ql, int qr, int k, int val){ if(ql > r || l > qr) return; if(ql <= l && r <= qr){ S[k] = max(S[k], val); lazy[k] = max(lazy[k], val); return; } int mid = l+r>>1; push(k); upd2(l, mid, ql, qr, k<<1, val); upd2(mid+1, r, ql, qr, k<<1|1, val); T[k] = max(T[k<<1], T[k<<1|1]); S[k] = min(S[k<<1], S[k<<1|1]); } int get_min(int l, int r, int k, int lim){ if(l == r){ return l; } int mid = l+r>>1; push(k); if(S[k<<1] < lim){ return get_min(l, mid, k<<1, lim); } return get_min(mid + 1, r, k<<1|1, lim); } int get(int l, int r, int ql, int qr, int k){ if(ql > r || l > qr) return 0; if(ql <= l && r <= qr) return T[k]; int mid = l+r>>1; return max(get(l, mid, ql, qr, k<<1), get(mid+1, r, ql, qr, k<<1|1)); } void solve(){ cin >> n >> d; vi val; for(int i = 1; i <= n; ++i){ cin >> a[i]; val.pb(a[i]); } sort(all(val)); val.erase(unique(all(val)), val.end()); for(int i = 1; i <= n; ++i){ a[i] = lower_bound(all(val), a[i]) - val.begin() + 1; } int m = val.size(); build(1, m, 1); for(int i = 1; i <= n; ++i){ int lim = i - d; while(S[1] < lim){ int pos = get_min(1, m, 1, lim); upd(1, m, pos, 1, 0, MOD); } upd2(1, m, a[i], m, 1, i); int mx = max(1, get(1, m, 1, a[i] - 1, 1) + 1); upd(1, m, a[i], 1, mx, i); } cout << T[1]; } int main(){ cin.tie(0); ios::sync_with_stdio(0); int tt = 1, aa; // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); while(tt--){ solve(); en; } cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n"; return 0; }
#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...