# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
62772 | Tenuun | Money (IZhO17_money) | C++17 | 313 ms | 152412 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>
using namespace std;
int tr[1000001], a[1000000];
void update(int ind, int val){
while(ind<=1000000){
tr[ind]+=val;
ind+=ind&-ind;
}
}
int get(int ind){
int ans=0;
while(ind){
ans+=tr[ind];
ind-=ind&-ind;
}
return ans;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
memset(tr, 0, sizeof tr);
int n, res=0, x, start=0, mx=0;
cin >> n;
for(int i=0; i<n; i++) cin >> a[i];
for(int i=0; i<n; i++){
start=i;
mx=a[i];
//cout << i << " ";
res++;
while(i+1<n && a[i+1]>=mx && get(a[i+1]-1)-get(a[start])<=0){
i++;
mx=max(mx, a[i]);
}
for(int j=start; j<=i; j++){
update(a[j], 1);
}
}
cout << res;
return 0;
}
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... |