| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 521014 | Wayne_Yan | Global Warming (CEOI18_glo) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#define int long long
typedef int64_t ll;
typedef long double ld;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pb emplace_back
#define mp make_pair
#define mt make_tuple
#define pii pair<int,int>
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define RF(n) RFi(i,n)
#define RFi(i,n) RFl(i,0,n)
#define RFl(i,l,n) for(int i=n-1;i>=l;i--)
#define all(v) begin(v),end(v)
#define siz(v) (ll(v.size()))
#define get_pos(v,x) (lower_bound(all(v),x)-begin(v))
#define sort_uni(v) sort(begin(v),end(v)),v.erase(unique(begin(v),end(v)),end(v))
#define mem(v,x) memset(v,x,sizeof v)
#define ff first
#define ss second
#define mid ((l+r)>>1)
#define RAN(a,b) uniform_int_distribution<int> (a, b)(rng)
#define debug(x) (cerr << (#x) << " = " << x << "\n")
#define cmax(a,b) (a = max(a,b))
#define cmin(a,b) (a = min(a,b))
template <typename T> using max_heap = __gnu_pbds::priority_queue<T,less<T> >;
template <typename T> using min_heap = __gnu_pbds::priority_queue<T,greater<T> >;
template <typename T> using rbt = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
signed main(){
int n,x;
cin >> n >> x;
int arr[n];
int rev[n];
F(n) cin >> arr[i];
F(n) rev[i] = -arr[n-1-i];
int ans = 0;
pii suf[n]; // (length, greatest)
vector<int> v;
F(n){
int c = get_pos(v, rev[i]);
if(c == (int)v.size()){
v.pb(rev[i]);
}else{
cmin(v[c], rev[i]);
}
suf[n-1-i] = mp((int)v.size(), -v.back());
}
//F(n) printf("%d %d\n", suf[i].ff, suf[i].ss);
v.clear();
F(n){
int c = get_pos(v, arr[i]);
if( c == (int) v.size()){
v.pb(arr[i]);
}else{
cmin(v[c], arr[i]);
}
if(i == n-1) break;
int bruh = get_pos(v, suf[i+1].ss + x);
if(bruh != (int)v.size() && v[bruh] == suf[i+1].ss + x) bruh--;
cmax(ans, suf[i+1].ff + bruh);
}
cmax(ans, (int)v.size());
printf("%lld", ans);
return 0;
}
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#define int long long
typedef int64_t ll;
typedef long double ld;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pb emplace_back
#define mp make_pair
#define mt make_tuple
#define pii pair<int,int>
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define RF(n) RFi(i,n)
#define RFi(i,n) RFl(i,0,n)
#define RFl(i,l,n) for(int i=n-1;i>=l;i--)
#define all(v) begin(v),end(v)
#define siz(v) (ll(v.size()))
#define get_pos(v,x) (lower_bound(all(v),x)-begin(v))
#define sort_uni(v) sort(begin(v),end(v)),v.erase(unique(begin(v),end(v)),end(v))
#define mem(v,x) memset(v,x,sizeof v)
#define ff first
#define ss second
#define mid ((l+r)>>1)
#define RAN(a,b) uniform_int_distribution<int> (a, b)(rng)
#define debug(x) (cerr << (#x) << " = " << x << "\n")
#define cmax(a,b) (a = max(a,b))
#define cmin(a,b) (a = min(a,b))
template <typename T> using max_heap = __gnu_pbds::priority_queue<T,less<T> >;
template <typename T> using min_heap = __gnu_pbds::priority_queue<T,greater<T> >;
template <typename T> using rbt = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
signed main(){
int n,x;
cin >> n >> x;
int arr[n];
int rev[n];
F(n) cin >> arr[i];
F(n) rev[i] = -arr[n-1-i];
int ans = 0;
pii suf[n]; // (length, greatest)
vector<int> v;
F(n){
int c = get_pos(v, rev[i]);
if(c == (int)v.size()){
v.pb(rev[i]);
}else{
cmin(v[c], rev[i]);
}
suf[n-1-i] = mp((int)v.size(), -v.back());
}
//F(n) printf("%d %d\n", suf[i].ff, suf[i].ss);
v.clear();
F(n){
int c = get_pos(v, arr[i]);
if( c == (int) v.size()){
v.pb(arr[i]);
}else{
cmin(v[c], arr[i]);
}
if(i == n-1) break;
int bruh = get_pos(v, suf[i+1].ss + x);
if(bruh != (int)v.size() && v[bruh] == suf[i+1].ss + x) bruh--;
cmax(ans, suf[i+1].ff + bruh);
}
cmax(ans, (int)v.size());
printf("%lld", ans);
return 0;
}