oj.uz

Submission #676249

# Submission time Handle Problem Language Result Execution time Memory
676249 2022-12-29T22:31:09 Z stevancv Money (IZhO17_money) C++14
0 / 100
 1 ms 340 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 1e6 + 2;
const ll linf = 1e18;
struct fenwick {
    ll bit[N];
    void Add(int x, int y) {
        for (;x < N; x += x & (-x)) bit[x] += y;
    }
    ll Get(int x) {
        ll ans = 0;
        for (; x > 0; x -= x & (-x)) ans += bit[x];
        return ans;
    }
}f;
int a[N];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    vector<int> iid(n + 1);
    iota(iid.begin(), iid.end(), 0);
    sort(iid.begin(), iid.end(), [&] (int i, int j) {
        return a[i] < a[j];
    });
    vector<int> id(n + 1);
    for (int i = 1; i <= n; i++) id[iid[i]] = i;
    int ans = 0;
    for (int i = n; i >= 1; ) {
        int j = i - 1;
        ll sta = f.Get(id[i]) + id[i];
        while (j > 0 && f.Get(id[j]) + id[j] == sta - i + j) j--;
        ans++;
        f.Add(1, i - j);
        f.Add(id[j + 1], j - i);
        i = j;
    }
    cout << ans << en;
    return 0;
}

Subtask #1
0 / 9.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 55.0

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