oj.uz

Submission #873102

# Submission time Handle Problem Language Result Execution time Memory
873102 2023-11-14T13:06:59 Z sleepntsheep Money (IZhO17_money) C++17
0 / 100
 1 ms 2648 KB 
#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.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 55.0

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