Submission #950035

#TimeUsernameProblemLanguageResultExecution timeMemory
950035PragmatismMoney (IZhO17_money)C++17
100 / 100
1327 ms58340 KiB
//Bismillahir-Rahmanir-Rahim #include <bits/stdc++.h> #pragma comment(linker, "/stack:200000000") #pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops") #pragma GCC target("sse,sse2,sse3,sse4,sse4.1,sse4.2,popcnt,avx,avx2") #define pb push_back #define pii pair <int, int> #define pll pair <long long, long long> #define pld pair <long double, long double> #define ll long long #define ld long double #define x first #define y second #define all(v) v.begin(),v.end() #define sz(s) (int)s.size() #define skip continue #define bpop(x) (ll)__builtin_popcountll(x) using namespace std; const int N = 1e6 + 7; const int M = 1e5 + 7; const int maxA = 1e5 + 7; const int inf = 1e9 + 7; const ll INF = 2e18 + 7; const int MOD = 998244353; const ld eps = 1e-9; pii dir[] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //clock_t start = clock(); //#define int long long int n, a[N]; int calc() { multiset <int> st; for (int i = 1;i <= n;i++)st.insert(a[i]); int ans = 0; for (int i = 1;i <= n;) { int pos = i; while (pos < n && a[pos + 1] == a[pos])pos++; auto it = st.lower_bound(a[i]); while (pos < n) { if (it != st.begin() && a[pos + 1] == *prev(it))it = prev(it), pos++; else break; } for (int j = i;j <= pos;j++)st.erase(st.find(a[j])); i = pos + 1, ans++; } return ans; } void solve() { cin >> n; for (int i = 1;i <= n;i++)cin >> a[i]; reverse(a + 1, a + n + 1); cout << calc(); } signed main() { //srand(time(NULL)); ios_base::sync_with_stdio(0); cin.tie(0); //freopen("subsequence.in", "r", stdin); //freopen("subsequence.out", "w", stdout); int test = 1; //cin >> test; for (int t = 1;t <= test;t++) { //cout << "Case " << t << ": "; solve(); } return 0; }

Compilation message (stderr)

money.cpp:4: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    4 | #pragma comment(linker, "/stack:200000000")
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...