Submission #1100483

#TimeUsernameProblemLanguageResultExecution timeMemory
1100483MuhammetMoney (IZhO17_money)C++17
0 / 100
1 ms2396 KiB
#include <bits/stdc++.h> using namespace std; #define ff first #define ss second const int N = 1e6 + 5; int n, b[N], vis[N], in[N]; int main(){ cin >> n; vector <int> a(n+1); vector <pair<int,int>> v; for(int i = 1; i <= n; i++){ cin >> a[i]; v.push_back({a[i],i}); } sort(v.begin(), v.end()); for(int i = 0; i < n-1; i++){ b[v[i].ff] = v[i+1].ff; } int cnt = 0; for(int i = 1; i <= n; i++){ if(vis[i] == 0){ cnt++; vis[i] = cnt; } if((i < n) and (a[i] == a[i+1] or b[a[i]] == a[i+1])){ vis[i+1] = cnt; } // cout << vis[i] << ' '; } // cout << '\n'; for(int i = 0; i < n; i++){ // cout << vis[v[i].ss] << ' '; in[vis[v[i].ss]] = i; } cnt = n; // cout << '\n'; for(int i = 0; i < n-1; i++){ if(vis[v[i].ss] != vis[v[i+1].ss]){ if(vis[in[vis[v[i+1].ss]]+1]+1 == vis[v[i].ss]){ // cout << i << ' '; cnt--; } if(vis[in[vis[v[i+1].ss]]+1] < vis[v[i+1].ss] and vis[v[i+1].ss] > vis[v[i].ss]){ cnt--; } else if(vis[v[i].ss]+1 == vis[v[i+1].ss]){ cnt--; } } else { cnt--; } } cout << cnt; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...