Submission #798199

#TimeUsernameProblemLanguageResultExecution timeMemory
798199BidoTeimaMoney (IZhO17_money)C++17
0 / 100
1 ms212 KiB
#include <bits/stdc++.h> typedef long long ll; using namespace std; const int N = 1e6 + 3; int st[4 * N]; int query(int ql, int qr, int l, int r, int node){ if(l > qr || r < ql) return 0; if(ql <= l && r <= qr){ return st[node]; } int mid = (l + r) >> 1; return query(ql, qr, l, mid, 2 * node + 1) + query(ql, qr, mid + 1, r, 2 * node + 2); } void update(int i, int x, int l, int r, int node){ if(i < l || i > r){ return; } if(l == r){ st[node]+=x; return; } int mid = (l + r) >> 1; update(i, x, l, mid, 2 * node + 1); update(i, x, mid + 1, r, 2 * node + 2); st[node] = st[2 * node + 1] + st[2 * node + 2]; } int main() { int n; cin>>n; int a[n]; map<int,int>mp{}; for(int i = 0; i < n; i++)cin>>a[i],mp[a[i]]; int cur=0; for(auto&it:mp){ it.second=cur++; } for(int i = 0; i < n; i++)update(mp[a[i]],1,0,(int)mp.size()-1,0); int ans=0,i=n-1; while(true){ while(i>=1){ int x = mp[a[i]], y = mp[a[i - 1]]; --i; if(x == y || query(0, y, 0, (int)mp.size()-1, 0) + 1 == query(0, x, 0, (int)mp.size()-1, 0)){ update(x,-1,0,(int)mp.size()-1,0); continue; } else{update(x,-1,0,(int)mp.size()-1,0); break;} } ans++; if(i == 0)break; } cout<<ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...