oj.uz

Submission #377074

# Submission time Handle Problem Language Result Execution time Memory
377074 2021-03-12T23:29:26 Z ijxjdjd Money (IZhO17_money) C++14
0 / 100
 3 ms 4224 KB 
#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;

multiset<int> lft;
const int MAXN = (int)(1e6);
int arr[MAXN + 5];
int cnt[MAXN+5];
int bk[MAXN+5];
int findLess(int i) {
    if (i == -1 || cnt[i] != 0) {
        return i;
    }
    else {
        return (bk[i] = findLess(bk[i]));
    }
}
int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);
	int N;
//	N = (int)(1e6);
	cin >> N;
	FR(i, N) {
	    cin >> arr[i];
	    cnt[arr[i]]++;
//	    arr[i] = N-i;
    }
    for (int i = 0; i < MAXN; i++) {
        bk[i] = i-1;
    }
    int lst = arr[N-1];
    int ans = 1;
    bool ori = true;
    for (int i = N-2; i >= 0; i--) {
        cnt[arr[i+1]]--;
        if (lst == arr[i]) {

        }
        else {
            int f = findLess(lst);
            if (f == arr[i]) {
                if (cnt[lst]) {
                    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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4204 KB Output is correct
2 Correct 3 ms 4204 KB Output is correct
3 Correct 3 ms 4224 KB Output is correct
4 Incorrect 3 ms 4204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4204 KB Output is correct
2 Correct 3 ms 4204 KB Output is correct
3 Correct 3 ms 4224 KB Output is correct
4 Incorrect 3 ms 4204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4204 KB Output is correct
2 Correct 3 ms 4204 KB Output is correct
3 Correct 3 ms 4224 KB Output is correct
4 Incorrect 3 ms 4204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4204 KB Output is correct
2 Correct 3 ms 4204 KB Output is correct
3 Correct 3 ms 4224 KB Output is correct
4 Incorrect 3 ms 4204 KB Output isn't correct
5 Halted 0 ms 0 KB -