Submission #676238

#	Time	Username	Problem	Language	Result	Execution time	Memory
676238		stevancv	Money (IZhO17_money)	C++14	0 / 100	0 ms	340 KiB

money

#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) {
        if (x == 0) return;
        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;
    }
    ll Val(int x) {
        return Get(x) - Get(x - 1);
    }
}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;
    for (int i = 1; i <= n; i++) f.Add(i, i);
    int ans = 0;
    for (int i = n; i >= 1; ) {
        int j = i - 1;
        int sta = f.Val(id[i]);
        while (j > 0 && f.Val(id[j]) == sta - i + j) j--;
        ans++;
        f.Add(id[j + 1] - 1, i - j);
        i = j;
    }
    cout << ans << en;
    return 0;
}

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