Submission #270517

#	Time	Username	Problem	Language	Result	Execution time	Memory
270517		limabeans	Bubble Sort 2 (JOI18_bubblesort2)	C++17	Compilation error	0 ms	0 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl


#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//*find_by_order: iterator to kth elem (0-indexed)
//order_of_key: # of items < k (stictly less)


using ll = long long;

const ll mod = 1e9+7;
const int maxn = 1e6 + 5;



bool sorted(vector<int> a) {
    int n = a.size();
    for (int i=1; i<n; i++) {
	if (a[i] < a[i-1]) return false;
    }
    return true;
}

int brute(vector<int> a) {
    int n = a.size();
    int res = 0;
    while (!sorted(a)) {
	res++;
	for (int i=0; i<n-1; i++) {
	    if (a[i] > a[i+1]) swap(a[i], a[i+1]);
	}
    }
    return res;
}

int solve(vector<int> a) {
    vector<int> sa = a;
    int n = a.size();
    sort(sa.begin(), sa.end());
    map<int,vector<int>> inds;
    for (int i=n-1; i>=0; i--) {
	inds[sa[i]].push_back(i);
    }
    int mx = 0;

    for (int i=0; i<n; i++) {
	int to = inds[a[i]].back();
	if (to < i) {
	    mx = max(mx, i-to);
	}
	inds[a[i]].pop_back();
    }

    return mx;
}

int solveInversion(vector<int> a) {
    map<int,int> ind;
    ordered_set<pair<int,int>> os;
    int hi = 0;
    
    for (int x: a) {
	pair<int,int> cur = {x, ind[x]++};
	int lte = os.order_of_key(cur);
	int inv = int(os.size()) - lte;
	hi = max(hi, inv);
	os.insert(cur);
    }

    return hi;
}


void print(vector<int> a) {
    for (int i: a) cout<<i<<" ";
    cout<<endl;
}



vector<int> solveTask3(vector<int> A, vector<int> X, vector<int> V) {
    //cerr<<"task3"<<endl;
    
    int n = A.size();
    vector<set<int>> inds(102);
    for (int i=0; i<n; i++) {
	inds[A[i]].insert(i);
    }

    vector<int> ans;

    for (int q=0; q<(int)X.size(); q++) {
	int idx = X[q];
	int val = V[q];
	inds[A[idx]].erase(idx);
	A[idx] = val;
	inds[A[idx]].insert(idx);

	int mx = 0;
	int prev = 0;
	for (int i=1; i<=100; i++) {
	    if (inds[i].empty()) {
		continue;
	    }
	    int dest = prev + int(inds[i].size()) - 1;
	    int dist = *inds[i].rbegin() - dest;
	    mx = max(mx, dist);
	    prev += int(inds[i].size());
	}
	//assert(mx == brute(A));
	ans.push_back(mx);
    }

    return ans;
}

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
    if (max(*max_element(A.begin(),A.end()), *max_element(V.begin(),V.end())) <= 100) {
    	return solveTask3(A,X,V);
    }
    int Q = X.size();
    vector<int> res(Q);
    for (int i=0; i<Q; i++) {
	A[X[i]] = V[i];
	res[i] = solveInversion(A);
	// assert(res[i] == brute(A));
    }

    return res;
}


int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    int n,q;
    cin>>n>>q;
    vector<int> a(n);
    for (int i=0; i<n; i++) {
	cin>>a[i];
    }
    vector<int> x, v;
    while (q--) {
	int i, val;
	cin>>i>>val;
	x.push_back(i);
	v.push_back(val);
    }

    auto res = countScans(a,x,v);
    for (int i: res) cout<<i<<" ";
    cout<<endl;
    
    
    return 0;
}

Compilation message (stderr)

/tmp/ccHMpy98.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccAMXePM.o:bubblesort2.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status