# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
166401 | abil | Money (IZhO17_money) | C++14 | 2 ms | 376 KiB |
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 fr first
#define sc second
#define pb push_back
#define mk make_pair
#define all(s) s.begin(),s.end()
#define int long long
using namespace std;
const int N = (1e6 + 12);
const int mod = (1e9 + 7);
const int INF = (1e15 + 9);
int t[N], a[N], n, cnt[N];
void update(int ind){
for(;ind <= n; ind = ind + (ind & (-ind))){
t[ind]++;
}
}
int get(int pos){
int res = 0;
for(;pos >= 1; pos = pos - (pos & (-pos))){
res += t[pos];
}
return res;
}
inline int sum(int l, int r) {
if(l == r) {
return 0;
}
return get(r - 1) - get(l);
}
main()
{
int ans = 0;
cin >> n;
for(int i = 1;i <= n; i++){
scanf("%lld", &a[i]);
}
int i = 1;
while(i <= n){
int j = i + 1;
ans++;
while(j <= n && a[j] >= a[j - 1] && sum(a[i], a[j]) == 0){
j++;
}
while(i < j) {
update(a[i]);
i++;
}
}
cout << ans;
}
Compilation message (stderr)
# | 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... |