oj.uz

Submission #925323

# Submission time Handle Problem Language Result Execution time Memory
925323 2024-02-11T12:20:05 Z boris_mihov Bubble Sort 2 (JOI18_bubblesort2) C++17
17 / 100
 9000 ms 4444 KB 
#include "bubblesort2.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <stack>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;

template <typename T>
using OSet = tree <T, null_type, std::less <T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long llong;
const int MAXN = 500000 + 10;
const int INF  = 1e9;

int n, q;
int in[MAXN];
int order[MAXN];
llong a[MAXN];

std::vector <int> countScans(std::vector <int> A, std::vector <int> X, std::vector <int> V)
{
    n = A.size();
    q = X.size();

    for (int i = 1 ; i <= n ; ++i)
    {
        a[i] = A[i - 1];
    }

    std::vector <int> answer(q, 0);
    for (int query = 0 ; query < q ; ++query)
    {
        OSet <llong> s;
        a[X[query] + 1] = V[query];
        for (int i = 1 ; i <= n ; ++i)
        {
            answer[query] = std::max(answer[query], (int)s.size() - (int)s.order_of_key(n * a[i] + i));
            s.insert(n * a[i] + i);
        }
    }

    return answer;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 348 KB Output is correct
2 Correct 113 ms 492 KB Output is correct
3 Correct 736 ms 852 KB Output is correct
4 Correct 731 ms 608 KB Output is correct
5 Correct 721 ms 616 KB Output is correct
6 Correct 768 ms 604 KB Output is correct
7 Correct 741 ms 612 KB Output is correct
8 Correct 742 ms 604 KB Output is correct
9 Correct 713 ms 608 KB Output is correct
10 Correct 620 ms 616 KB Output is correct
11 Correct 610 ms 604 KB Output is correct
12 Correct 608 ms 616 KB Output is correct
13 Correct 605 ms 612 KB Output is correct
14 Correct 620 ms 852 KB Output is correct
15 Correct 605 ms 616 KB Output is correct
16 Correct 612 ms 604 KB Output is correct
17 Correct 605 ms 852 KB Output is correct
18 Correct 641 ms 616 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 348 KB Output is correct
2 Correct 113 ms 492 KB Output is correct
3 Correct 736 ms 852 KB Output is correct
4 Correct 731 ms 608 KB Output is correct
5 Correct 721 ms 616 KB Output is correct
6 Correct 768 ms 604 KB Output is correct
7 Correct 741 ms 612 KB Output is correct
8 Correct 742 ms 604 KB Output is correct
9 Correct 713 ms 608 KB Output is correct
10 Correct 620 ms 616 KB Output is correct
11 Correct 610 ms 604 KB Output is correct
12 Correct 608 ms 616 KB Output is correct
13 Correct 605 ms 612 KB Output is correct
14 Correct 620 ms 852 KB Output is correct
15 Correct 605 ms 616 KB Output is correct
16 Correct 612 ms 604 KB Output is correct
17 Correct 605 ms 852 KB Output is correct
18 Correct 641 ms 616 KB Output is correct
19 Execution timed out 9014 ms 1112 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 9034 ms 4444 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 348 KB Output is correct
2 Correct 113 ms 492 KB Output is correct
3 Correct 736 ms 852 KB Output is correct
4 Correct 731 ms 608 KB Output is correct
5 Correct 721 ms 616 KB Output is correct
6 Correct 768 ms 604 KB Output is correct
7 Correct 741 ms 612 KB Output is correct
8 Correct 742 ms 604 KB Output is correct
9 Correct 713 ms 608 KB Output is correct
10 Correct 620 ms 616 KB Output is correct
11 Correct 610 ms 604 KB Output is correct
12 Correct 608 ms 616 KB Output is correct
13 Correct 605 ms 612 KB Output is correct
14 Correct 620 ms 852 KB Output is correct
15 Correct 605 ms 616 KB Output is correct
16 Correct 612 ms 604 KB Output is correct
17 Correct 605 ms 852 KB Output is correct
18 Correct 641 ms 616 KB Output is correct
19 Execution timed out 9014 ms 1112 KB Time limit exceeded
20 Halted 0 ms 0 KB -