제출 #1257297

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1257297		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;

    vector<int> b = a;
    sort(b.begin(), b.end());

    ordered_set<pair<int, int>> st;
    for (int i = 0; i < n; i++) st.insert(make_pair(b[i], i));

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

    auto count_less = [&](int x) {
        return (int)st.order_of_key(make_pair(x, INT_MIN));
    };

    auto adjacent = [&](int x, int y) {
        if (x == y) return count_less(x + 1) - count_less(x) >= 2;
        if (x > y) swap(x, y);
        return count_less(y) == count_less(x + 1);
    };

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

        int j = i;
        if (j - 1 >= 1 && a[j - 1] <= a[j] && adjacent(a[j], a[j - 1])) j -= 1;

        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