Submission #319268

#TimeUsernameProblemLanguageResultExecution timeMemory
319268kshitij_sodaniMoney (IZhO17_money)C++14
45 / 100
1561 ms152768 KiB
#include <bits/stdc++.h> using namespace std; typedef long long llo; #define mp make_pair #define pb push_back #define a first #define b second //#define endl '\n' int n; int it[1000001]; int tree[1000001*4]; pair<int,int> pp[1000001]; int ans[1000001]; int re[1000001]; //int mi[1000001][20]; void build(int no,int l,int r){ if(l==r){ tree[no]=it[l]; } else{ int mid=(l+r)/2; build(no*2+1,l,mid); build(no*2+2,mid+1,r); tree[no]=max(tree[no*2+1],tree[no*2+2]); } } int query(int no,int l,int r,int aa,int bb){ if(r<aa){ return -1; } if(aa<=l){ if(tree[no]<=bb){ return -1; } if(l==r){ return l; } } int mid=(l+r)/2; int x=query(no*2+1,l,mid,aa,bb); if(x==-1){ return query(no*2+2,mid+1,r,aa,bb); } else{ return x; } } vector<int> pre[1000001]; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cin>>n; /*for(int i=0;i<n;i++){ for(int j=0;j<20;j++){ mi[i][j]=1; } }*/ for(int i=0;i<n;i++){ cin>>it[i]; } vector<pair<int,int>> ss; vector<pair<pair<int,int>,int>> tt; set<int> kk; build(0,0,n-1); int cur=0; for(int i=0;i<n;i++){ while(ss.size()){ if(ss.back().a<=it[i]){ ss.pop_back(); } else{ break; } } pp[i]={-1,-1}; if(ss.size()){ int ne=ss.back().b; tt.pb({{ne,i-1},cur}); //cur++; int jj=*kk.upper_bound(it[i]); pp[i]={ss.back().b,jj}; /* int low=query(0,0,n-1,i,jj); if(low!=-1){ tt.pb({{i,low-1},cur}); //cur++; }*/ } kk.insert(it[i]); ss.pb({it[i],i}); } vector<pair<int,int>> cc; set<pair<int,int>> dd; for(int i=n-1;i>=0;i--){ while(cc.size()){ if(cc.back().a<=it[i]){ dd.erase(cc.back()); cc.pop_back(); } else{ break; } } re[i]=-1; if(cc.size()){ re[i]=cc.back().b; if(pp[i].a!=-1){ if(cc[0].a>pp[i].b){ auto j=dd.lower_bound({pp[i].b+1,0}); /* int ind=0; for(int j=19;j>=0;j--){ if(ind+(1<<j)<cc.size()){ if(cc[ind+(1<<j)].a>pp[i].b){ ind+=(1<<j); } } }*/ tt.pb({{i,(*j).b-1},cur}); } } } /* if(cc.size()){ re[i]=cc.back().b; if(pp[i].a!=-1){ int cur2=cc.back().b; while(cur2!=-1){ if(it[cur2]>pp[i].b){ // cout<<i<<":"<<cur2<<endl; tt.pb({{i,cur2-1},cur}); break; } cur2=re[cur2]; } }*/ /*if(pp[i].a!=-1){ if(cc[0].a>pp[i].b){ if(cc.back().a<=pp[i].b){ ans[i]=ans[cc.back().b]; } else{ ans[i]=cc.back().b; } tt.pb({{i,ans[i]-1},cur}); } }*/ //} dd.insert({it[i],i}); cc.pb({it[i],i}); } /* for(int i=0;i<n;i++){ if(pp[i].b==-1){ continue; } for(int j=i+1;j<n;j++){ if(it[j]>pp[i].b){ if(j!=re[pp[i].a]){ while(true){ continue; } } tt.pb({{i,j-1},cur}); break; } } if(pp[i].a!=-1){ if(re[pp[i].a]!=-1){ int cur2=re[pp[i].a]; tt.pb({{i,cur2-1},cur}); } } } */ for(auto j:tt){ pre[j.a.b].pb(j.a.a); } int ans=1; int ma=-1; for(int i=0;i<n-1;i++){ for(auto j:pre[i]){ if(j<=ma){ continue; } ans+=1; ma=i; } } cout<<ans<<endl; 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...