oj.uz

Submission #361198

# Submission time Handle Problem Language Result Execution time Memory
361198 2021-01-28T15:42:17 Z BartolM Bubble Sort 2 (JOI18_bubblesort2) C++17
17 / 100
 9000 ms 1900 KB 
#include "bubblesort2.h"
#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const int N=2005;

int n, q;
vector <int> sol;
vector <int> saz;
int F[2*N];

int query(int x) {
    int ret=0;
    for (; x>0; x-=x&-x) ret+=F[x];
    return ret;
}

void update(int x, int val) {
    for (; x<=n+q; x+=x&-x) F[x]+=val;
}

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

    saz=V;
    for (int x:A) saz.pb(x);
    sort(saz.begin(), saz.end());
    saz.erase(unique(saz.begin(), saz.end()), saz.end());

    for (int i=0; i<n; ++i) A[i]=lower_bound(saz.begin(), saz.end(), A[i])-saz.begin()+1;
    for (int i=0; i<q; ++i) V[i]=lower_bound(saz.begin(), saz.end(), V[i])-saz.begin()+1;

    for (int i=0; i<q; ++i) {
        A[XX[i]]=V[i];

        memset(F, 0, sizeof F);
        int maxi=0;
        for (int j=0; j<n; ++j) {
            int curr=j-query(A[j]);
            maxi=max(maxi, curr);
            update(A[j], 1);
        }
        sol.pb(maxi);
    }

    return sol;

}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 364 KB Output is correct
2 Correct 16 ms 364 KB Output is correct
3 Correct 100 ms 492 KB Output is correct
4 Correct 101 ms 620 KB Output is correct
5 Correct 98 ms 620 KB Output is correct
6 Correct 94 ms 620 KB Output is correct
7 Correct 99 ms 492 KB Output is correct
8 Correct 98 ms 492 KB Output is correct
9 Correct 97 ms 492 KB Output is correct
10 Correct 96 ms 492 KB Output is correct
11 Correct 87 ms 508 KB Output is correct
12 Correct 86 ms 492 KB Output is correct
13 Correct 83 ms 620 KB Output is correct
14 Correct 86 ms 492 KB Output is correct
15 Correct 84 ms 492 KB Output is correct
16 Correct 97 ms 492 KB Output is correct
17 Correct 84 ms 492 KB Output is correct
18 Correct 83 ms 492 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 364 KB Output is correct
2 Correct 16 ms 364 KB Output is correct
3 Correct 100 ms 492 KB Output is correct
4 Correct 101 ms 620 KB Output is correct
5 Correct 98 ms 620 KB Output is correct
6 Correct 94 ms 620 KB Output is correct
7 Correct 99 ms 492 KB Output is correct
8 Correct 98 ms 492 KB Output is correct
9 Correct 97 ms 492 KB Output is correct
10 Correct 96 ms 492 KB Output is correct
11 Correct 87 ms 508 KB Output is correct
12 Correct 86 ms 492 KB Output is correct
13 Correct 83 ms 620 KB Output is correct
14 Correct 86 ms 492 KB Output is correct
15 Correct 84 ms 492 KB Output is correct
16 Correct 97 ms 492 KB Output is correct
17 Correct 84 ms 492 KB Output is correct
18 Correct 83 ms 492 KB Output is correct
19 Runtime error 7 ms 1260 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1784 ms 940 KB Output is correct
2 Execution timed out 9082 ms 1900 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 364 KB Output is correct
2 Correct 16 ms 364 KB Output is correct
3 Correct 100 ms 492 KB Output is correct
4 Correct 101 ms 620 KB Output is correct
5 Correct 98 ms 620 KB Output is correct
6 Correct 94 ms 620 KB Output is correct
7 Correct 99 ms 492 KB Output is correct
8 Correct 98 ms 492 KB Output is correct
9 Correct 97 ms 492 KB Output is correct
10 Correct 96 ms 492 KB Output is correct
11 Correct 87 ms 508 KB Output is correct
12 Correct 86 ms 492 KB Output is correct
13 Correct 83 ms 620 KB Output is correct
14 Correct 86 ms 492 KB Output is correct
15 Correct 84 ms 492 KB Output is correct
16 Correct 97 ms 492 KB Output is correct
17 Correct 84 ms 492 KB Output is correct
18 Correct 83 ms 492 KB Output is correct
19 Runtime error 7 ms 1260 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -