# include <bits/stdc++.h>
# define pb push_back
# define fr first
# define sc second
# define mk make_pair
using namespace std;
const long long linf = 1e18 + 7;
const int inf = 1e9 + 7;
const int N = 1e6 + 5;
typedef long long ll;
int n, a[N], t[N * 4], ans = 1;
void update(int pos, int v = 1, int tl = 1, int tr = n){
if(tl == tr)
t[v] ++;
else{
int tm = (tl + tr) >> 1;
if(pos <= tm)
update(pos, v << 1, tl, tm);
else
update(pos, (v << 1) | 1, tm + 1, tr);
t[v] = t[v << 1] + t[(v << 1) | 1];
}
}
int get(int l, int r, int v = 1, int tl = 1, int tr = n){
if(l > tr || tl > r) return 0;
if(l <= tl && tr <= r) return t[v];
int tm = (tl + tr) >> 1;
return get(l, r, v << 1, tl, tm) +
get(l, r, (v << 1) | 1, tm + 1, tr);
}
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i ++)
scanf("%d", &a[i]);
int f = 1;
update(a[1]);
for(int i = 2; i <= n; i ++){
if(a[i] < a[i - 1]) ans ++, f = i;
else {
int sum = get(a[f] + 1, a[i] - 1);
if(sum) ans ++, f = i;
}
update(a[i]);
}
cout << ans << endl;
}
Compilation message
money.cpp: In function 'int main()':
money.cpp:40:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
^
money.cpp:43:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a[i]);
^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
21548 KB |
Output is correct |
2 |
Incorrect |
0 ms |
21548 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
21548 KB |
Output is correct |
2 |
Incorrect |
0 ms |
21548 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
21548 KB |
Output is correct |
2 |
Incorrect |
0 ms |
21548 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
21548 KB |
Output is correct |
2 |
Incorrect |
0 ms |
21548 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |