Submission #377070

#	Time	Username	Problem	Language	Result	Execution time	Memory
377070		ijxjdjd	Money (IZhO17_money)	C++14	45 / 100	1597 ms	51180 KiB

money

#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
#define all(x) begin(x), end(x)

using namespace std;

using ll = long long;

map<int, int> lft;
const int MAXN = (int)(1e6);
int arr[MAXN + 5];
int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);
	int N;
	cin >> N;
	FR(i, N) {
	    cin >> arr[i];
        lft[arr[i]]++;
    }
    int lst = arr[N-1];
    int ans = 1;
    bool ori = true;
    for (int i = N-2; i >= 0; i--) {
        int& a = lft[arr[i+1]];
        bool gone = false;
        a--;
        if (a == 0) {
            lft.erase(arr[i+1]);
            gone = true;
        }
        if (lst == arr[i]) {

        }
        else {
            auto it = lft.lower_bound(lst);
            if (it != lft.begin() && (*prev(it)).first == arr[i]) {
                if (!gone) {
                    if (ori) {
                        ori = false;
                    }
                    else {
                        ans++;
                        ori = true;
                    }
                }
                else {
                    ori = false;
                }
            }
            else {
                ans++;
                ori = true;
            }
        }
        lst = arr[i];

    }
    cout << ans << '\n';
	return 0;
}

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