Submission #789397

#	Time	Username	Problem	Language	Result	Execution time	Memory
789397		anton	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	3349 ms	136000 KiB

bubblesort2

#include<bits/stdc++.h>
#include "bubblesort2.h"

using namespace std;
#define pii pair<int, int>


const int INF = (1<<30)-1;

struct Tree{
    vector<int> tree;
    vector<int> d;
    int m;

    Tree(vector<int> &v){
        int m = 1;
        while(m<v.size()){
            m*=2;
        }
        m*=2;

        tree.resize(m);
        d.resize(m);

        build(v, 0, v.size()-1, 1);
    }

    void build(vector<int> &v, int lt, int rt, int t){
        if(lt == rt){
            tree[t] = v[lt];
            d[t] = 0;
        }
        else{
            int mid = (lt+rt)/2;
            d[t] = 0;

            build(v, lt, mid, t*2);
            build(v, mid+1, rt, t*2+1);
            tree[t] = min(tree[t*2], tree[t*2+1]) +d[t];
        }
    }

    int update(int l, int r, int v, int lt, int rt, int t){
        if(l<=lt && rt<=r){
            d[t] += v;
            tree[t] += v;
            return tree[t];
        }
        else if(rt<l || r<lt){
            return INF;
        }
        else{
            int mid = (lt+rt)/2;
            update(l, r, v, lt, mid, t*2);
            update(l, r, v, mid+1, rt, t*2+1);
            tree[t] = min(tree[t*2], tree[t*2+1]) + d[t];
            return tree[t];
        }
    }

	void set_val(int id, int v, int lt, int rt, int t){
		if(lt == id && rt == id){
			tree[t] = v;
		}
		else{
			int mid =(lt+rt)/2;

			if(id<=mid){
				set_val(id, v-d[t], lt, mid, t*2);
			}
			else{
				set_val(id, v-d[t], mid+1, rt, t*2+1);
			}


			tree[t] = min(tree[t*2], tree[t*2+1])+d[t];
		}
	}
};

struct SumTree{
    vector<int> tree;
    int m;

    SumTree(vector<int> &v){
        int m = 1;
        while(m<v.size()){
            m*=2;
        }
        m*=2;

        tree.resize(m);

        build(v, 0, v.size()-1, 1);
    }

    void build(vector<int> &v, int lt, int rt, int t){
        if(lt == rt){
            tree[t] = v[lt];
        }
        else{
            int mid = (lt+rt)/2;

            build(v, lt, mid, t*2);
            build(v, mid+1, rt, t*2+1);
            tree[t] = tree[t*2] + tree[t*2+1];
        }
		//cout<<"buit "<<lt<<" "<<rt<<" "<<tree[t]<<endl;
    }

    int get_sum(int l, int r, int lt, int rt, int t){

		//cout<<"sum "<<lt<<" "<<rt<<" "<<tree[t]<<endl;
        if(l<=lt && rt<=r){
            return tree[t];
        }
        else if(rt<l || r<lt || l>r){
            return 0;
        }
        else{
            int mid = (lt+rt)/2;
            return get_sum(l, r, lt, mid, t*2) + get_sum(l, r, mid+1, rt, t*2+1);
        }
    }

	void add_val(int id, int v, int lt, int rt, int t){
		if(lt == id && rt == id){
			tree[t] += v;
		}
		else{
			int mid =(lt+rt)/2;

			if(id<=mid){
				add_val(id, v, lt, mid, t*2);
			}
			else{
				add_val(id, v, mid+1, rt, t*2+1);
			}
			tree[t] = tree[t*2] + tree[t*2+1];
		}
	}
};
int n, q;
vector<pii> big;
map<pii, int> small;

vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){
	n = A.size();
    q=X.size();
	
    for(int i = 0; i<n; i++){
        big.push_back(pii(A[i], i));
    }
    for(int i = 0; i<q; i++){
        big.push_back(pii(V[i], X[i]));
    }

    sort(big.begin(), big.end());
    int bs = big.size();

    vector<int> v(bs, INF);
    
    for(int i = 0; i<bs; i++){
        small[big[i]] = i;
    }

    vector<pii> target(n);
    for(int i = 0; i<n; i++){
        target[i] = pii(A[i], i);
    }
    sort(target.begin(), target.end());
	vector<int> oc(bs, 0);
    for(int i = 0; i<n; i++){
        v[small[target[i]]] = i-target[i].second;
		oc[small[target[i]]] =1;
    }

    /*for(int i = 0; i<bs; i++){
        cout<<big[i].first<<" "<<big[i].second<<" "<<v[i]<<" "<<oc[i]<<endl;
    }*/
    Tree tr = Tree(v);
	SumTree s_tr = SumTree(oc);
	s_tr.get_sum(0, bs-1, 0, bs-1, 1);

	vector<int> r;
	for(int i = 0; i<q; i++){
		int cur_pos = small[pii(A[X[i]], X[i])];
		int pos = small[pii(V[i], X[i])];

		//cout<<"from "<<cur_pos<<" to "<<pos<<endl;
		A[X[i]] = V[i];

		if(cur_pos<pos){
			tr.update(cur_pos, pos, -1, 0, bs-1, 1);
		}
		else{
			tr.update(pos, cur_pos, 1, 0, bs-1, 1);
		}
		s_tr.add_val(cur_pos, -1, 0, bs-1, 1);
		s_tr.add_val(pos, 1, 0, bs-1, 1);

		int tar = s_tr.get_sum(0, pos-1, 0, bs-1, 1);
		//cout<<"new tar "<<tar<<endl;
		tr.set_val(cur_pos, INF, 0, bs-1, 1);
		tr.set_val(pos, tar-X[i], 0, bs-1, 1);

		r.push_back(-tr.tree[1]);
	}
	
	return r;
}

Compilation message (stderr)

bubblesort2.cpp: In constructor 'Tree::Tree(std::vector<int>&)':
bubblesort2.cpp:17:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |         while(m<v.size()){
      |               ~^~~~~~~~~
bubblesort2.cpp: In constructor 'SumTree::SumTree(std::vector<int>&)':
bubblesort2.cpp:87:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         while(m<v.size()){
      |               ~^~~~~~~~~

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