Submission #1257341

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257341		proofy	Money (IZhO17_money)	C++20	0 / 100	0 ms	324 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;

        auto check = [&](int k) {
            for (int j = i - 1; j >= k; --j) if (a[j] > a[j + 1])
                return false;
            
            vector<pair<int, int>> b = {{a[k], 1}};
            for (int j = k + 1; j <= i; j++) if (a[j] == a[j - 1]) b.back().second += 1;
            else b.emplace_back(a[j], 1);

            if ((int)b.size() == 1) return st[b[0].first] >= b[0].second;
            if (st[b[0].first] < b[0].second) return false;
            if (st[b.back().first] < b.back().second) return false;
            
            for (int j = 1; j < (int)b.size() - 1; j++) {
                auto [x, y] = b[j];
                if (st[x] != y) return false;
            }
            return true;
        };

        int j = i;
        int l = 1, r = i;
        if (check(l)) j = l;
        else {
            while (r - l > 1) {
                int m = (l + r) / 2;
                if (check(m)) r = m;
                else l = m;
            }
            j = r;
        }

        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