Submission #786644

#TimeUsernameProblemLanguageResultExecution timeMemory
786644vqpahmadMoney (IZhO17_money)C++14
100 / 100
351 ms30668 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define ll long long #define pii pair<int,int> #define F first #define S second #define endl '\n' #define pb push_back #define sz(a) (int)a.size() #define all(a) a.begin(),a.end() const int mod = 1e9 + 7; const int N = 1e6 + 3; const ll inf = 1e18; const int off = (1<<20); int t[off*2]; int combine(int u,int v){ return u+v; } void update(int i,int u){ i+=off; t[i] = u; while (i/=2){ t[i] = combine(t[i*2],t[i*2+1]); } } int get(int l, int r, int idx=1, int lo=0, int hi=off){ if (lo>=r||hi<=l) return 0; if (lo>=l&&hi<=r) return t[idx]; int mi = (lo+hi)/2; return combine(get(l,r,idx*2,lo,mi),get(l,r,idx*2+1,mi,hi)); } int32_t main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin >> n; vector<int> a(n); for (int i=0;i<n;i++){ cin >> a[i]; } int ans = 0; for (int i=0;i<n;){ ans++; int b = i; i++; while (i<n&&a[i]>=a[i-1]&&get(a[b]+1,a[i])==0){ i++; } for (int j=b;j<i;j++) update(a[j],1); } cout << ans << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...