Submission #270490

#	Time	Username	Problem	Language	Result	Execution time	Memory
270490		limabeans	Bubble Sort 2 (JOI18_bubblesort2)	C++17	39 / 100	9085 ms	5656 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





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;
}


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];
	//print(A);
	//cout<<solve(A)<<" ans: "<<brute(A)<<endl;
	//assert(brute(A) == solve(A));

	res[i] = solve(A);
    }

    return res;
}


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

    //out(brute({7, 4, 6, 3, 1, 3, 1, 8, 9, 8 }));

    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;
}

*/

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