Submission #84368

#	Time	Username	Problem	Language	Result	Execution time	Memory
84368		bogdan10bos	Bubble Sort 2 (JOI18_bubblesort2)	C++14	38 / 100	9029 ms	4492 KiB

bubblesort2

#include <bits/stdc++.h>

//#define DEBUG

#ifndef DEBUG
#include "bubblesort2.h"
#endif

using namespace std;

int N, Q;

class Normalizer
{
public:
    map<int, int> mp;
    vector<int> ord;

    void clear() { mp.clear(); ord.clear(); }

    void add(int x)
    {
        if(mp.count(x)) return;
        mp[x];
        ord.push_back(x);
    }

    void normalize()
    {
        sort(ord.begin(), ord.end());
        for(int i = 0; i < ord.size(); i++)
            mp[ ord[i] ] = i + 1;
    }

    int get(int x) { return mp[x]; }
}nrm;

class BinaryIndexedTree
{
public:
    int N;
    int aib[1000005];

    void U(int pos, int val)
    {
        for(; pos <= N; pos += (pos & (-pos)))
            aib[pos] += val;
    }

    int Q(int pos)
    {
        int ans = 0;
        for(; pos > 0; pos -= (pos & (-pos)))
            ans += aib[pos];
        return ans;
    }

    void clear()
    {
        for(int i = 0; i <= N; i++) aib[i] = 0;
    }
}aib;

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V)
{
	N = A.size(), Q = V.size();
	vector<int> ret;
	ret.resize(Q);
	for(int i = 0; i < N; i++)  nrm.add(A[i]);
	for(int i = 0; i < Q; i++)  nrm.add(V[i]);

	nrm.normalize();
	int K = nrm.ord.size() + 1;
	aib.N = K;
	aib.clear();

	for(int i = 0; i < N; i++)  A[i] = nrm.get(A[i]);
	for(int q = 0; q < Q; q++)
    {
        int pos = X[q];
        int val = nrm.get(V[q]);
        A[pos] = val;

        aib.clear();
        int mx = 0;
        for(int i = 0; i < N; i++)
        {
            mx = max(mx, aib.Q(K) - aib.Q(A[i]));
            aib.U(A[i], 1);
        }

        ret[q] = mx;
    }

    return ret;
}

#ifdef DEBUG
int readInt(){
	int i;
	if(scanf("%d",&i)!=1){
		fprintf(stderr,"Error while reading input\n");
		exit(1);
	}
	return i;
}

int main(){

    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);

	int N,Q;
	N=readInt();
	Q=readInt();

	std::vector<int> A(N);
	for(int i=0;i<N;i++)
		A[i]=readInt();

	std::vector<int> X(Q),V(Q);
	for(int j=0;j<Q;j++){
		X[j]=readInt();
		V[j]=readInt();
	}

	std::vector<int> res=countScans(A,X,V);

	for(int j=0;j<int(res.size());j++)
		printf("%d\n",res[j]);
}
#endif

Compilation message (stderr)

bubblesort2.cpp: In member function 'void Normalizer::normalize()':
bubblesort2.cpp:31:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < ord.size(); i++)
                        ~~^~~~~~~~~~~~

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