Submission #108494

#TimeUsernameProblemLanguageResultExecution timeMemory
108494shashwatchandraMoney (IZhO17_money)C++17
0 / 100
32 ms31744 KiB
/*input 8 3 2 3 2 3 2 3 2 */ #include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define int long long #define double long double #define f first #define s second #define mp make_pair #define pb push_back #define RE(i,n) for (int i = 1; i <= n; i++) #define RED(i,n) for (int i = n; i > 0; i--) #define REPS(i,n) for(int i = 1; (i*i) <= n; i++) #define REP(i,n) for (int i = 0; i < (int)n; i++) #define FOR(i,a,b) for (int i = a; i < b; i++) #define REPD(i,n) for (int i = n-1; i >= 0; i--) #define FORD(i,a,b) for (int i = a; i >= b; i--) #define all(v) v.begin(),v.end() #define pii pair<int,int> #define vi vector<int> #define vvi vector<vi> #define print(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout << *it << " "; cout << endl; #define debug(x) cout << x << endl; #define debug2(x,y) cout << x << " " << y << endl; #define debug3(x,y,z) cout << x << " " << y << " " << z << endl; typedef tree< int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; const int INF = 1e18+1; const int MOD = 1e9+7; const double PI = 3.14159265358979323846264338; int raise(int a,int n,int m = MOD){ if(n == 0)return 1; if(n == 1)return a; int x = 1; x *= raise(a,n/2,m); x %= m; x *= x; x %= m; if(n%2)x*= a; x %= m; return x; } int floor1(int n,int k){ if(n%k == 0 || n >= 0)return n/k; return (n/k)-1; } int ceil1(int n,int k){ return floor1(n+k-1,k); } const int N = 1e6+1; int n; int a[N]; int seg[4*N]; int mark[N]; bool done[N]; #define mid (l+r)/2 void add(int node,int l,int r,int ind){ if(ind < l or ind > r)return; if(l == r and r == ind){ seg[node]++; return; } add(2*node,l,mid,ind);add(2*node+1,mid+1,r,ind); seg[node] = seg[2*node]+seg[2*node+1]; } int query(int node,int l,int r,int start,int end){ if(l > end or r < start)return 0; if(l >= start and r <= end)return seg[node]; return query(2*node,l,mid,start,end)+query(2*node+1,mid+1,r,start,end); } #undef mid bool check(int i,int j){ if(abs(a[i]-a[j]) < 2)return 1; if(query(1,1,N-1,a[i]+1,a[j]-1))return 0; return 1; } void solve(){ cin >> n; // mark[n+1] = INF; REP(i,4*N)seg[i] = 0; RE(i,n){ cin >> a[i]; done[i] = 0; if(i == 1)mark[i] = 1; else{ mark[i] = mark[i-1]+(a[i] < a[i-1]); } // cout << mark[i] << " "; } //cout << endl; int ans = 0; int j = 2; int donetill = 0; RE(i,n){ if(donetill >= i){ add(1,1,N-1,a[i]); continue; } while(check(i,j)){ j++; if(j == n+1)break; if(mark[i] != mark[j])break; } donetill = j-1; //cout << i << ": " << j << endl; ans++; add(1,1,N-1,a[i]); } cout << ans; } signed main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); //freopen(".in","r",stdin);freopen(".out","w",stdout); int t = 1; //cin >> t; while(t--){ solve(); } 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...