Submission #375428

#TimeUsernameProblemLanguageResultExecution timeMemory
375428muhi1112Po (COCI21_po)C++17
70 / 70
86 ms10348 KiB
#include <bits/stdc++.h> using namespace std; #define f1 first #define s2 second #define INF 1e9+10 #define ll long long #define pb push_back #define fri(a) freopen(a,"r",stdin) #define fro(a) freopen(a,"w",stdout) const int N=2e5+5; ll n,dizi[N]; pair<ll,int>t[4*N]; void build(int v,int tl,int tr){ if(tl==tr)t[v]={dizi[tl],tl}; else{ int tm=(tl+tr)/2; build(v*2,tl,tm); build(v*2+1,tm+1,tr); t[v]=min(t[v*2],t[v*2+1]); } } pair<ll,int> getmin(int v,int tl,int tr,int l,int r){ if(l>r)return {INF,-1}; if(l==tl && r==tr)return t[v]; int tm=(tl+tr)/2; return min(getmin(v*2,tl,tm,l,min(r,tm)),getmin(v*2+1,tm+1,tr,max(l,tm+1),r)); } int solve(int l,int r,int y){ //cout<<l<<" "<<r<<endl; if(l>r)return 0; //cout<<l<<" "<<r<<endl; pair<ll,int> x=getmin(1,0,n,l,r); return solve(l,x.s2-1,x.f1)+solve(x.s2+1,r,x.f1)+(y!=x.f1); } int main(){ // fri("in.txt"); // fro("out.txt"); cin>>n; for(int i=0;i<n;i++){ cin>>dizi[i]; } build(1,0,n); cout<<solve(0,n,-1)-1<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...