제출 #612233

#제출 시각아이디문제언어결과실행 시간메모리
612233Andyvanh1Global Warming (CEOI18_glo)C++14
62 / 100
131 ms14412 KiB
#include <bits/stdc++.h> using namespace std; #define vt vector #define pb push_back #define all(x) x.begin(),x.end() #define FORR1(x) for(int i = 0; i < (x); i++) #define FORR2(j,x) for(int (j) = 0; (j) < (x); (j)++) #define f first #define s second typedef vt<int> vi; typedef long long ll; typedef long double ld; typedef pair<int,int> pii; map<int,vi> mp; map<int,int> dic; int pp[10005]; int sz[10005]; int cst[10005]; int ans[10005][103]; int find(int x){ return (x==pp[x] ? x : pp[x] = find(pp[x])); } void join(int a, int b){ if(find(a)==find(b))return; int u = find(a), v = find(b); if(sz[u]>sz[v])swap(u,v); pp[u] = v; sz[v]+=sz[u]; } int arr[200005]; int in2[200005]; int out2[200005]; int in1[200005]; int out1[200005]; void solve(){ int n, x; cin>>n>>x; FORR1(n)cin>>arr[i]; set<int,greater<>> st2; for(int i = n-1; i>=0; i--){ auto it = st2.lower_bound(arr[i]); if(it == st2.end()){ in2[i] = arr[i]; out2[i] = -1; st2.insert(arr[i]); }else{ in2[i] = arr[i]; out2[i] = *it; st2.erase(it); st2.insert(arr[i]); } } set<int> st1; FORR1(n){ auto it = st1.lower_bound(arr[i]); if(it == st1.end()){ in1[i] = arr[i]; out1[i] = -1; st1.insert(arr[i]); }else{ in1[i] = arr[i]; out1[i] = *it; st1.erase(it); st1.insert(arr[i]); } } int a = st1.size(), b = st2.size(); vi cal1(a), cal2(b); FORR1(a)cal1[i] = -1; int att = 0; for(auto & e: st2){ cal2[att] = e; att++; } int ans = b; int at1 = -1, at2 = b-1; FORR1(n){ int l = 0, r = a; while(l!=r){ int mid = (l+r)>>1; if(cal1[mid]==-1||(out1[i]!=-1&&out1[i]<cal1[mid])){ r = mid; }else if(cal1[mid]==out1[i]){ l = mid; r = mid; }else{ l = mid+1; } } cal1[l] = in1[i]; l = 0; r = b; while(l!=r){ int mid = (l+r)>>1; if(cal2[mid]>in2[i]){ l = mid+1; }else if(cal2[mid]<in2[i]){ r = mid; }else{ l = r = mid; } } cal2[l] = out2[i]; if(at1==-1){ if(cal2[at2]==-1){ at2--; } if(cal1[0]-cal2[at2]<x){ at1 = 0; } }else if(at2!=-1){ if(cal2[at2]==-1){ at2--; } if(cal1[at1]-cal2[at2]<x){ if(at1!=a-1&&cal1[at1+1]!=-1&&cal1[at1+1]-cal2[at2]<x){ at1++; } }else{ at2--; } } ans = max(ans, at1+at2+2); /*if(at1+at2+2==6){ cout<<i<<'\n'; cout<<at1<<' '<<at2<<'\n'; }*/ } ans = max(ans,(int)st1.size()); cout<<ans<<'\n'; } int main() { cin.tie(nullptr); ios_base::sync_with_stdio(false); 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...
#Verdict Execution timeMemoryGrader output
Fetching results...