Submission #1257329

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257329		proofy	Money (IZhO17_money)	C++20	0 / 100	0 ms	472 KiB

money

#include <bits/stdc++.h>
using namespace std;
#define ll long long

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
template <class T>
using ordered_set = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>;
// find_by_order((int)k) returns iterator of the kth element
// order_of_key((T)key) returns the number of elements less than this key


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int& u : a) cin >> u;

    map<int, int> st;
    for (int i = 0; i < n; i++) st[a[i]] += 1;

    a.insert(a.begin(), 0);

    auto adjacent = [&](int x, int y) {
        if (x == y) return st[x] >= 2;
        if (x > y) swap(x, y);
        auto iter = st.lower_bound(y);
        if (iter == st.begin()) return false;
        return prev(iter)->first == x;
    };

    auto erase_element = [&](int x) {
        st[x] -= 1;
        if (st[x] == 0) st.erase(x);
    };
    
    function<int(int)> solve = [&](int i) {
        if (i == 0) return 0;

        int j = i;
        int cnt = 1;
        while (j - 1 >= 1) {
            if (a[j - 1] == a[j]) {
                if (st[a[j]] >= cnt + 1) {
                    cnt += 1;
                    j -= 1;
                }
                else break;
            } else {
                if (adjacent(a[j - 1], a[j])) {
                    cnt = 1;
                    j -= 1;
                } else break;
            }
        }

        for (int k = j; k <= i; k++) erase_element(a[k]);

        return 1 + solve(j - 1);
    };

    cout << solve(n) << "\n";
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 16
• Subtask 3: 0 / 20
• Subtask 4: 0 / 55