| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1276203 | Bui_Quoc_Cuong | Financial Report (JOI21_financial) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<=(int)b;i++)
#define FORD(i,a,b) for(int i=a;i>=(int)b;i--)
#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(a) a.begin(),a.end()
#define BIT(mask,i) ((mask>>(i))&1)
#define MASK(a) (1LL<((a)))
#define uni(v) sort(all(v)); v.resize(unique(all(v)) - v.begin())
#define pii pair <int, int>
#define vi vector <int>
#define vl vector <ll>
template <class A,class B>
bool maximize(A &a, const B b)
{
if(a < b){ a = b; return 1;} return 0;
}
template <class A,class B>
bool minimize(A &a, const B b)
{
if(a > b){ a = b; return 1;} return 0;
}
const int maxn = 3e5 + 5;
int n, d;
int a[maxn], dp[maxn];
namespace sub1
{
void solve()
{
for(int i = 1; i <= n; i++)
{
int cur = 0;
dp[i] = 1;
for(int j = i - 1; j >= 1; j--)
{
if(a[j] > a[i]) cur++;
else cur = 0;
if(cur >= d) break;
if(a[j] < a[i]) maximize(dp[i], dp[j] + 1);
}
}
cout << *max_element(dp + 1, dp + 1 + n);
}
}
namespace sub2
{
struct Node
{
int head, tail, len, max_len, max_pre, max_suf;
Node()
{
head = tail = - 1;
len = max_len = max_pre = max_suf = 0;
}
friend Node operator + (Node a, Node b)
{
Node ans;
ans.len = a.len + b.len;
ans.head = a.head;
ans.tail = b.tail;
ans.max_len = max(a.max_len, b.max_len);
if(a.tail == b.head && a.tail == 1) ans.max_len = max(ans.max_len, a.max_suf + b.max_pre);
ans.max_pre = a.max_pre;
if(a.tail == b.head && a.tail == 1 && a.len == a.max_pre) ans.max_pre = a.len + b.max_pre;
ans.max_suf = b.max_suf;
if(a.tail == b.head && a.tail == 1 && b.len == b.max_suf) ans.max_suf = a.max_suf + b.len;
return ans;
}
} st[4 * maxn];
void build(int id, int l, int r)
{
if(l == r)
{
st[id].len = 1;
st[id].head = st[id].tail = 1;
st[id].max_pre = st[id].max_suf = st[id].max_len = 1;
return;
}
int mid = (l + r) >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
st[id] = st[id << 1] + st[id << 1 | 1];
}
void del(int pos)
{
int id = 1, l = 1, r = n;
while(l < r)
{
int mid = (l + r) >> 1;
if(pos <= mid) id = id << 1, r = mid;
else id = id << 1 | 1, l = mid + 1;
}
st[id].max_pre = st[id].max_suf = st[id].max_len = st[id].head = st[id].tail = 0;
while(id > 1)
{
id >>= 1;
st[id] = st[id << 1] + st[id << 1 | 1];
}
}
Node get(int id, int l, int r, int u, int v)
{
if(l > v || r < u) return Node();
if(l >= u && r <= v) return st[id];
int mid = (l + r) >> 1;
return get(id << 1, l, mid, u, v) + get(id << 1 | 1, mid + 1, r, u, v);
}
int tree[4 * maxn];
void update(int pos, int val)
{
int id = 1, l = 1, r = n;
while(l < r)
{
int mid = (l + r) >> 1;
if(pos <= mid) id = id << 1, r = mid;
else id = id << 1 | 1, l = mid + 1;
}
tree[id] = val;
while(id > 1)
{
id >>= 1;
tree[id] = max(tree[id << 1], tree[id << 1 | 1]);
}
}
int get_max_dp(int id, int l, int r, int u, int v)
{
if(l > v || r < u) return 0;
if(l >= u && r <= v) return tree[id];
int mid = (l + r) >> 1;
return max(get_max_dp(id << 1, l, mid, u, v), get_max_dp(id << 1 | 1, mid + 1, r, u, v));
}
void solve()
{
vector <pii> zip_val;
FOR(i, 1, n) zip_val.pb(make_pair(a[i], i));
sort(all(zip_val));
build(1, 1, n);
FOR(i, 0, zip_val.size() - 1)
{
int j = i;
while(j <= (int)zip_val.size() - 1 && zip_val[j].first == zip_val[i].first) j++;
j--;
FOR(it, i, j)
{
int id = zip_val[it].second;
del(id);
}
FOR(it, i, j)
{
int id = zip_val[it].second;
int l = 1, r = id, pos = id;
while(l <= r)
{
int mid = (l + r) >> 1;
if(get(1, 1, n, mid, id).max_len < d) pos = mid, r = mid - 1;
else l = mid + 1;
}
dp[id] = get_max_dp(1, 1, n, pos, id) + 1;
}
FOR(it, i, j)
{
int id = zip_val[it].second;
update(id, dp[id]);
}
i = j;
}
cout << *max_element(dp + 1, dp + 1 + n);
}
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#define kieuoanh "kieuoanh"
if(fopen(kieuoanh".inp","r"))
{
freopen(kieuoanh".inp","r",stdin);
freopen(kieuoanh".out","w",stdout);
}
cin >> n >> d;
for(int i = 1; i <= n; i++) cin >> a[i];
vi values;
for(int i = 1; i <= n; i++) values.pb(a[i]);
uni(values);
for(int i = 1; i <= n; i++) a[i] = upper_bound(all(values), a[i]) - values.begin();
return sub2::solve();
return 0;
}