# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
144055 | 2019-08-15T21:19:54 Z | The_Wolfpack | Money (IZhO17_money) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h> using namespace std; const int NMAX=1e6+8; int fen[NMAX]; void add(int x) { for(;x<NMAX;x+=(x&-x)) fen[x]++; } int gget(int x) { int res=0; for(;x>0;x-=(x&-x)) res+=fen[x]; return res; } int n,a[NMAX]; int main() { ios_base::sync_with_stdio(false); cin>>n; int res=1; vector<int>tmp; for(int i=1;i<=n;i++) { cin>>a[i]; if(!tmp.size()) { tmp.push_back(a[i]); continue; } else { if(a[i]<tmp.back() || gget(a[i]-1)>gget(tmp[0]) { res++; for(int x:tmp) add(x); tmp.clear(); } tmp.push_back(a[i]); } } cout<<res<<endl; return 0; }