Submission #873102

#	Time	Username	Problem	Language	Result	Execution time	Memory
873102		sleepntsheep	Money (IZhO17_money)	C++17	0 / 100	1 ms	2648 KiB

money

#include <iostream>
#include <cassert>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>

using i64 = long long;
using u64 = unsigned long long;
using f64 = double;
using f80 = long double;

using namespace std;
#define ALL(x) x.begin(), x.end()
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
#define N 1000000
#define A 1000000

int n, a[N], t[A+2];

int search(int x)
{
    int p = 0, s = 0;
    for (int j = 1 << 21; j >>= 1;) if (p + j < A + 2 && s + t[p + j] < x) s += t[p += j];
    return p + 1;
}

int qry(int p)
{
    int z {0};
    for (; p; p-=p&-p) z += t[p];
    return z;
}

void update(int p, int k)
{
    for (; p < A + 2; p +=p&-p) t[p] += k;
}

int main()
{
    ShinLena;
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i];

    for (int i = n; i--;)
    {
        int k = qry(a[i]);
        int p = search(k+1);
        if (p >= A + 2); else update(p, -1);
        update(a[i], 1);
    }
    cout << qry(A);

    return 0;
}

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