This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#define DEBUG 1
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;
const int INF=0x3f3f3f3f;
const int N=1e6+5;
const int OFF=(1<<20);
int n;
int T[2*OFF];
int dp[N], p[N];
int query(int a, int b, int pos=1, int lo=0, int hi=OFF) {
if (lo>=a && hi<=b) return T[pos];
if (lo>=b || hi<=a) return 0;
int mid=(lo+hi)/2;
return query(a, b, pos*2, lo, mid)+query(a, b, pos*2+1, mid, hi);
}
void update(int pos, int val) {
for (pos+=OFF; pos; pos/=2) T[pos]+=val;
}
void solve() {
p[0]=INF;
dp[0]=0;
int lef=0;
for (int i=1; i<=n; ++i) {
if (p[i]<p[i-1] || query(p[lef]+1, p[i])) {
for (int j=lef; j<i; ++j) if (j) update(p[j], 1);
lef=i;
}
dp[i]=dp[lef-1]+1;
}
printf("%d\n", dp[n]);
}
void load() {
scanf("%d", &n);
for (int i=1; i<=n; ++i) scanf("%d", &p[i]);
}
int main() {
load();
solve();
return 0;
}
Compilation message (stderr)
money.cpp: In function 'void load()':
money.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
50 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
money.cpp:51:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
51 | for (int i=1; i<=n; ++i) scanf("%d", &p[i]);
| ~~~~~^~~~~~~~~~~~~
# | 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... |