Submission #361198

#	Time	Username	Problem	Language	Result	Execution time	Memory
361198		BartolM	Bubble Sort 2 (JOI18_bubblesort2)	C++17	17 / 100	9082 ms	1900 KiB

bubblesort2

#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 / 17
• Subtask 2: 0 / 21
• Subtask 3: 0 / 22
• Subtask 4: 0 / 40