제출 #892534

#제출 시각아이디문제언어결과실행 시간메모리
892534quochuy147Financial Report (JOI21_financial)C++14
5 / 100
488 ms41988 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define ll long long #define mp make_pair #define pb push_back #define pii pair<int, int> #define pll pair<ll, ll> #define MASK(i) (1LL << (i)) #define BIT(x, i) (((x) >> (i)) & 1) #define all(x) (x).begin() , (x).end() #define TIME (1.0 * clock() / CLOCKS_PER_SEC) #define file "name" template <typename T1, typename T2> bool minimize(T1 &a, T2 b){if (a > b) {a = b; return true;} return false;} template <typename T1, typename T2> bool maximize(T1 &a, T2 b){if (a < b) {a = b; return true;} return false;} const int inf = 1e9 + 5; const ll linf = 1e17; const int mod = 1e9 + 7; const int N = 3e5 + 5; const int LOG = 20; int n, d, res; int a[N], f[N], lim[N]; int rmq[N][LOG + 5], lg[N]; pii b[N]; set <pii> s; map <int, int> x; vector <int> pos[N]; void inp() { cin >> n >> d; for(int i = 1; i <= n; ++i) cin >> a[i]; } namespace sub4 { void prepare() { for(int i = 2; i <= n; ++i) lg[i] = lg[i / 2] + 1; for(int i = 1; i <= n; ++i) rmq[i][0] = a[i]; for(int j = 1; j <= LOG; ++j) for(int i = 1; i + MASK(j) - 1 <= n; ++i) rmq[i][j] = max(rmq[i][j - 1], rmq[i + MASK(j - 1)][j - 1]); } int get(int l, int r) { int k = lg[r - l + 1]; return max(rmq[l][k], rmq[r - MASK(k) + 1][k]); } void solve() { prepare(); for(int i = n; i >= 1; --i) { int l = i + 1, r = n, id = n + 1; while(l <= r) { int m = (l + r) >> 1; if(get(i, m) > a[i]) { id = m; r = m - 1; } else l = m + 1; } f[i] = f[id] + 1; maximize(res, f[i]); } cout << res; } } namespace sub5 { int x[N]; void solve() { for(int i = 1; i <= n; ++i) x[i] = inf; x[0] = -inf; for(int i = 1; i <= n; ++i) { int l = 1, r = n, id = 0; while(l <= r) { int m = (l + r) >> 1; if(x[m] >= a[i]) { id = m; r = m - 1; } else l = m + 1; } x[id] = a[i]; maximize(res, id); } cout << res; } } namespace sub3 { void solve() { a[0] = -1; for(int i = 1; i <= n; ++i) f[i] = 1; for(int i = 1; i <= n; ++i) { int id = i + d; maximize(res, f[i]); for(int j = i + 1; j <= n; ++j) { if(a[j] <= a[i]) { id = j + d; continue; } maximize(f[j], f[i] + 1); if(j >= id) break; } } cout << res; } } struct segtree { int st[4 * N]; segtree() {} void update(int id, int l, int r, int i, int v) { if(i < l || r < i) return ; if(l == r) return void(st[id] = v); int m = (l + r) >> 1; update(id << 1, l, m, i, v); update(id << 1 | 1, m + 1, r, i, v); st[id] = max(st[id << 1], st[id << 1 | 1]); } int walk_left(int id, int l, int r, int v) { if(r < v || st[id] == 0) return n + 1; if(l == r) return l; int m = (l + r) >> 1; int res = walk_left(id << 1, l, m, v); if(res == n + 1) res = walk_left(id << 1 | 1, m + 1, r, v); return res; } int walk_right(int id, int l, int r, int v) { if(v < l || st[id] == 0) return 0; if(l == r) return l; int m = (l + r) >> 1; int res = walk_right(id << 1 | 1, m + 1, r, v); if(!res) res = walk_right(id << 1, l, m, v); return res; } int get(int id, int l, int r, int u, int v) { if(v < l || r < u) return 0; if(l >= u && r <= v) return st[id]; int m = (l + r) >> 1; return max(get(id << 1, l, m, u, v), get(id << 1 | 1, m + 1, r, u, v)); } } st[2]; bool cmp(const pii &a, const pii &b) { if(a.fi == b.fi) return a.se > b.se; return a.fi < b.fi; } namespace sub6 { void solve() { for(int i = 1; i <= n; ++i) b[i] = mp(a[i], i); sort(b + 1, b + n + 1, cmp); s.insert({1, n - 1}); for(int i = 1; i <= n; ++i) { int id = b[i].se; st[0].update(1, 1, n, id, 1); int l = st[0].walk_right(1, 1, n, id - 1), r = st[0].walk_left(1, 1, n, id + 1); l++; r--; s.erase({l, r - l}); if(id - l > d) s.insert({l, id - l}); if(r - id > d) s.insert({id, r - id}); auto it = s.lower_bound({id, 0}); if(it == s.end()) lim[id] = n; else lim[id] = min(n, (*it).fi + d); } for(int i = 1; i <= n; ++i) { for(int p : pos[i]) st[1].update(1, 1, n, p, 0); int id = lower_bound(b + 1, b + n + 1, mp(a[i], 0)) - b; f[i] = st[1].get(1, 1, n, 1, id - 1) + 1; id += x[a[i]]; x[a[i]]++; st[1].update(1, 1, n, id, f[i]); pos[lim[i] + 1].pb(id); maximize(res, f[i]); } cout << res; } } void solve() { // if(n <= 7000) return void(sub3::solve()); // if(d == 1) return void(sub4::solve()); // if(d == n) return void(sub5::solve()); sub6::solve(); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); // freopen(file".inp" , "r" , stdin); // freopen(file".out" , "w" , stdout); inp(); solve(); 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...