Submission #925322

#	Time	Username	Problem	Language	Result	Execution time	Memory
925322		boris_mihov	Bubble Sort 2 (JOI18_bubblesort2)	C++17	17 / 100	9065 ms	2652 KiB

bubblesort2

#include "bubblesort2.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <stack>

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

int n, q;
int a[MAXN];
int in[MAXN];
int order[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)
    {
        a[X[query] + 1] = V[query];
        for (int i = 1 ; i <= n ; ++i)
        {
            int curr = 0;
            for (int j = 1 ; j < i ; ++j)
            {
                curr += (a[j] > a[i]);
            }

            answer[query] = std::max(answer[query], curr);
        }
    }

    return answer;
}

• Subtask 1: 17 / 17
• Subtask 2: 0 / 21
• Subtask 3: 0 / 22
• Subtask 4: 0 / 40