Submission #769324

#	Time	Username	Problem	Language	Result	Execution time	Memory
769324		Dan4Life	Bubble Sort 2 (JOI18_bubblesort2)	C++17	38 / 100	9053 ms	1876 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
using vi = vector<int>;
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
const int mxN = (int)2e4+10;
int fen[mxN];
void upd(int x, int v){
	for(; x<mxN; x+=x&-x) fen[x]+=v;
}

int sum(int x){ int s = 0; for(; x>0; x-=x&-x) s+=fen[x]; return s; }
int sum(int a, int b){
	if(a>b) return 0;
	return sum(b)-sum(a-1);
}

vi countScans(vi A, vi X, vi V){
    int q = sz(X), n = sz(A); vi ans, a(all(A));
	vector<int> v; 
	for(auto u : a) v.pb(u);
	for(int i = 0; i < q; i++) v.pb(V[i]);
	sort(all(v)); v.erase(unique(all(v)),end(v));
	for(int i = 0; i < q; i++) V[i]=(int)(lower_bound(all(v),V[i])-begin(v))+1;
	for(int i = 0; i < n; i++) a[i]=(int)(lower_bound(all(v),a[i])-begin(v))+1;
    for(int _ = 0; _ < q; _++){
        a[X[_]] = V[_];
        int tot = 0; fill(fen,fen+mxN,0);
        for(int i = 0; i < n; i++){
            tot = max(tot, sum(a[i]+1,mxN-1));
			upd(a[i],1);
        }
        ans.pb(tot);
    }
	return ans;
}

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