Submission #1152038

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152038		brover29	Bubble Sort 2 (JOI18_bubblesort2)	C++20	17 / 100	9093 ms	18544 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N=1e6+29;
vector<int>B;
ll st[4*N];
void build(ll v,ll l,ll r){
    if(l==r){
        st[v]=0;
        return;
    }
    ll mid=(r+l)>>1;
    build(v*2,l,mid);
    build(v*2+1,mid+1,r);
    st[v]=0;
}void upd(ll v,ll l,ll r,ll pos){
    if(l==r){
        st[v]++;
        return;
    }
    ll mid=(r+l)>>1;
    if(pos<=mid)upd(v*2,l,mid,pos);
    else upd(v*2+1,mid+1,r,pos);
    st[v]=st[v*2]+st[v*2+1];
}ll get(ll v,ll l,ll r,ll x,ll y){
    if(y<l||r<x)return 0;
    if(x<=l&&r<=y){
        return st[v];
    }
    ll mid=(r+l)/2;
    return (get(v*2,l,mid,x,y)+get(v*2+1,mid+1,r,x,y));
}map<ll,ll>mp;
set<ll>s;
ll timer;
vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){
	ll Q=X.size();
	for(ll i:A)s.insert(i);
	vector<int> answer;
	for (int j=0;j<Q;j++) {
		s.insert(V[j]);
		ll mx=0;
	}for(ll i:s){
        mp[i]=++timer;
	}for(auto &i:A)i=mp[i];
	for (int j=0;j<Q;j++) {
		A[X[j]]=mp[V[j]];
		ll mx=0;
		build(1,1,1e6);
		for(ll i:A){
            mx=max(mx,get(1,1,1e6,i+1,1e6));
            upd(1,1,1e6,i);
		}
		answer.push_back(mx);
	}
	return answer;
}

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