Submission #1192452

#TimeUsernameProblemLanguageResultExecution timeMemory
1192452TitanicXDzzPilot (NOI19_pilot)C++20
40 / 100
105 ms2796 KiB
#include<bits/stdc++.h> using namespace std; int l[1000010]; int r[1000010]; int dp[1000010]; pair<int,int> a[1000010]; int main(){ int n,q; cin>>n>>q; for(int i=1;i<=n;i++){ cin>>a[i].first; a[i].second=i; } sort(a+1,a+n+1); for(int i=1;i<=n;i++){ if(l[a[i].second-1]==0&&r[a[i].second+1]==0){ l[a[i].second]=a[i].second; r[a[i].second]=a[i].second; dp[i]=dp[i-1]+1; } else if(l[a[i].second-1]==0){ l[r[a[i].second+1]]=a[i].second; r[a[i].second]=r[a[i].second+1]; dp[i]=r[a[i].second]-a[i].second+1+dp[i-1]; } else if(r[a[i].second+1]==0){ r[l[a[i].second-1]]=a[i].second; l[a[i].second]=l[a[i].second-1]; dp[i]=a[i].second-l[a[i].second]+1+dp[i-1]; } else{ l[r[a[i].second+1]]=l[a[i].second-1]; r[l[a[i].second-1]]=r[a[i].second+1]; dp[i]=(a[i].second-l[a[i].second-1]+1)*(r[a[i].second+1]-a[i].second+1)+dp[i-1]; } } for(int i=1;i<=q;i++){ int x; cin>>x; int l=0; int r=n; while(l!=r){ int mid=(l+r+1)/2; if(x<a[mid].first) r=mid-1; else l=mid; } cout<<dp[l]<<endl; } }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...