#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;
int n,dizi[N],t[4*N];
map<int,vector<int>>mp;
void build(int v,int tl,int tr){
if(tl==tr)t[v]=dizi[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]);
}
}
ll getmin(int v,int tl,int tr,int l,int r){
if(l>r)return INF;
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){
//cout<<l<<" "<<r<<endl;
if(l>r)return 0;
if(l+1==r-1)return 1;
if(l+1==r)return 0;
ll x=getmin(1,1,n+1,l+1,r-1);
//cout<<x<<endl;
int a=solve(l,mp[x][0])+solve(mp[x][mp[x].size()-1],r)+1;
for(int i=1;i<mp[x].size();i++){
a+=solve(mp[x][i-1],mp[x][i]);
//cout<<"sa"<<endl;
}
return a;
}
int main(){
//fri("in.txt");
//fro("out.txt");
cin>>n;
for(int i=1;i<=n;i++){
cin>>dizi[i];
mp[dizi[i]].pb(i);
}
build(1,1,n+1);
cout<<solve(0,n+1)<<endl;
return 0;
}
Compilation message
Main.cpp: In function 'int solve(int, int)':
Main.cpp:40:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for(int i=1;i<mp[x].size();i++){
| ~^~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Runtime error |
741 ms |
524288 KB |
Execution killed with signal 9 |
| 3 |
Runtime error |
854 ms |
524288 KB |
Execution killed with signal 9 |
| 4 |
Execution timed out |
1127 ms |
455276 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1121 ms |
496108 KB |
Time limit exceeded |
| 6 |
Correct |
120 ms |
12652 KB |
Output is correct |
| 7 |
Incorrect |
140 ms |
20972 KB |
Output isn't correct |
