이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#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]);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
ll n, d;
cin >> n>> d;
if(d==1)
{
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]];
}
map<ll,ll> nxtmx;
for (int i = n-1; i >= 0; i--)
{
ll nxt = query(1, n, order[i]+1,n,0);
if(nxt == inf) nxtmx[i]=-1;
else nxtmx[i] = nxt;
update(1, n, order[i], i,0);
}
vector<ll> dp(n,1);
dp.back() = 1;
for (int i = n-2; i >= 0; i--)
{
if(nxtmx[i]!=-1) dp[i]+=dp[nxtmx[i]];
}
cout << *max_element(dp.begin(), dp.end()) << endl;
}
else{
vector<ll> a(n);
for(int i=0; i < n; i++) cin >> a[i];
vector<ll> dp(n,1);
dp.back() = 1;
for (int i = n-2; i >= 0; i--)
{
ll cur = 0;
for (int j=i+1; j < n; j++)
{
if(a[j] > a[i])
{
cur++;
dp[i] = max(dp[i], 1 + dp[j]);
if(cur == d)break;
}
else cur = 0;
}
}
cout << *max_element(dp.begin(), dp.end()) << endl;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |