제출 #1153636

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1153636		MPG	Global Warming (CEOI18_glo)	C++20	100 / 100	39 ms	6644 KiB

glo

#include <bits/stdc++.h>
using namespace std;
typedef long long                           ll;
#define                                     max_heap priority_queue<ll>
#define                                     min_heap priority_queue<pair <ll, ll>, vector<pair <ll, ll>>, greater<pair <ll, ll>>> // size(), push(), top(), pop();
//#define                                     min_heap priority_queue<ll, vector<ll>, greater<ll>>
#define                                     sariE cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
#define                                     filE freopen("fenceplan.in", "r", stdin); freopen("fenceplan.out", "w", stdout);
#define                                     endl '\n'
#define                                     md(a) (a % mod + mod) % mod
//cout << setprecision(5) << f;
ll const maxn = 2e5 + 110;
ll const inf = 2e18;
ll const loG = 23;
ll const mod = 1e9 + 7;//998244353; //1e9 + 9;
ll const sq = 500;
ll power(ll a, ll b, ll mod){if (b == 0) return 1; if (b == 1) return a; ll x = power(a, b / 2, mod); return (((x * x) % mod) * (b % 2 ? a : 1)) % mod;}



ll n, k, arr[maxn], ans[maxn];
vector <ll> dp, pd;

int main(){
sariE;// filE;

cin >> n >> k;
dp.resize(n + 10);
pd.resize(n + 10);
for (int i = 0; i < n + 10; i++){
    dp[i] = inf;
    pd[i] = inf;
}
for (int i = 0; i < n; i++){
    cin >> arr[i];
}

ll mx = 0;
for (int i = 0; i < n; i++){
    int j = lower_bound(dp.begin(), dp.end(), arr[i]) - dp.begin();
    dp[j] = arr[i];
    ans[i] = j + 1;
}

for (int i = n - 1; i >= 0; i--) {
    int pos = lower_bound(pd.begin(), pd.end(), -(arr[i] - k)) - pd.begin();
    mx = max(mx, ans[i] + pos);
    //cout << pos << ' ';
    int insert_pos = lower_bound(pd.begin(), pd.end(), -arr[i]) - pd.begin();
    pd[insert_pos] = -arr[i];
}
//cout << endl;
cout << mx << endl;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 25 / 25