제출 #920100

#제출 시각아이디문제언어결과실행 시간메모리
920100Sir_Ahmed_ImranGlobal Warming (CEOI18_glo)C++17
100 / 100
1171 ms92360 KiB
///~~~LOTA~~~/// #include <bits/stdc++.h> using namespace std; #define nl '\n' #define ff first #define ss second #define ll long long #define append push_back #define all(x) (x).begin(),(x).end() #define pii pair<int,int> #define N 200001 #define M 1000000001 int a[N]; int Q[N]; struct Node{ int val; Node *L,*R; }; Node* getnode(){ Node* temp=new Node; temp->val=0; temp->L=NULL; temp->R=NULL; return temp; } class ST{ public: Node* root=getnode(); void update(int& i,int& x,Node* v,int& s,int& e){ if(e-s==1){ v->val=x; return; } int mid=(s+e)/2; if(v->L==NULL) v->L=getnode(); if(v->R==NULL) v->R=getnode(); if(i<mid) update(i,x,v->L,s,mid); else update(i,x,v->R,mid,e); v->val=max(v->L->val,v->R->val); if(v->L->val==0){ delete v->L; v->L=NULL; } if(v->R->val==0){ delete v->R; v->R=NULL; } } int get(int& l,int& r,Node* v,int& s,int& e){ if(r<=s || e<=l || l>=r || v->val==0) return 0; if(l<=s && e<=r) return v->val; int mid=(s+e)/2; if(v->L==NULL) v->L=getnode(); if(v->R==NULL) v->R=getnode(); int o=max(get(l,r,v->L,s,mid),get(l,r,v->R,mid,e)); if(v->L->val==0){ delete v->L; v->L=NULL; } if(v->R->val==0){ delete v->R; v->R=NULL; } return o; } }; inline void solve(){ int n,m,o,p,q,r,s; cin>>n>>m; ST x,y; p=0; q=M; for(int i=o=1;i<=n;i++) cin>>a[i]; for(int i=n;i>0;i--){ r=a[i]+1; s=y.get(r,q,y.root,p,q)+1; Q[i]=y.get(a[i],r,y.root,p,q); y.update(a[i],s,y.root,p,q); } for(int i=1;i<=n;i++){ r=x.get(p,a[i],x.root,p,q)+1; y.update(a[i],Q[i],y.root,p,q); x.update(a[i],r,x.root,p,q); s=max(a[i]-m+1,p); o=max(o,r+y.get(s,q,y.root,p,q)); } cout<<o; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); 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...