This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define stop system("pause")
#define stop2 char o; cin >> o
#define INP freopen("pcb.in","r",stdin)
#define OUTP freopen ("pcb.out","w",stdout)
using namespace std;
const int maxn = 1e6+2;
vector<int> v;
int dp[maxn];
int bit[maxn];
namespace fen{
int bit[maxn];
void upd(int id,int x){
while(id < maxn){
bit[id]+=x;
id|=id+1;
}
}
int sum(int x){
int res = 0;
while(x>=0){
res+=bit[x];
x&=x+1;x--;
}
return res;
}
int segm(int l,int r){
int ans = sum(r);
if(l)ans-=sum(l-1);
return ans;
}
}
main(){
ios_base::sync_with_stdio(0);
int n; cin >> n;
vector<pair<int,int> > qwe;
int last = -1;
int cnt = 0;
for(int i(0); i < n;i++){
int x; cin >> x;
v.push_back(x);
if(x!=last && last!=-1){
qwe.push_back({last,cnt});
cnt = 0;
}else if(last == -1){
last = x;
cnt = 0;
}
cnt++;
}
dp[0] = 1;
int l = 0;
for(int i(1);i < n;i++){
if(v[i] < v[i-1]){
for(int z(l); z < i;z++)fen::upd(v[z],1);
l = i;
dp[i] = dp[i-1]+1;
continue;
}
while(1){
if(v[i]-v[l]>1){
int kek = fen::segm(v[l]+1,v[i]-1);
if(kek){
fen::upd(v[l],1);
l++;
}else break;
}else break;
}
dp[i] = dp[l-1]+1;
}
cout << dp[n-1];
}
/*
6
1 2 3 4
*/
Compilation message (stderr)
money.cpp:37:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){
^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |