oj.uz

Submission #925311

# Submission time Handle Problem Language Result Execution time Memory
925311 2024-02-11T11:34:07 Z boris_mihov Bubble Sort 2 (JOI18_bubblesort2) C++17
0 / 100
 9000 ms 3104 KB 
#include "bubblesort2.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

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

int n, q;
int a[MAXN];
int dp[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);
    for (int query = 0 ; query < q ; ++query)
    {
        a[X[query] + 1] = V[query];
        for (int i = n ; i >= 1 ; --i)
        {
            dp[i] = 1;
            for (int j = i + 1 ; j <= n ; ++j)
            {
                if (a[i] > a[j])
                {
                    dp[i] = std::max(dp[i], dp[j] + 1);
                }
            }

            answer[query] = std::max(answer[query], dp[i] - 1);
        }
    }

    return answer;
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 133 ms 2408 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 133 ms 2408 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 133 ms 2408 KB Output isn't correct
2 Halted 0 ms 0 KB -