oj.uz

Submission #270518

# Submission time Handle Problem Language Result Execution time Memory
270518 2020-08-17T17:13:37 Z limabeans Bubble Sort 2 (JOI18_bubblesort2) C++17
39 / 100
 9000 ms 4988 KB 
#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;
}
*/

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 384 KB Output is correct
2 Correct 300 ms 384 KB Output is correct
3 Correct 1917 ms 640 KB Output is correct
4 Correct 1945 ms 640 KB Output is correct
5 Correct 1954 ms 680 KB Output is correct
6 Correct 1807 ms 680 KB Output is correct
7 Correct 1849 ms 760 KB Output is correct
8 Correct 1940 ms 760 KB Output is correct
9 Correct 1877 ms 680 KB Output is correct
10 Correct 1730 ms 676 KB Output is correct
11 Correct 1700 ms 680 KB Output is correct
12 Correct 1698 ms 676 KB Output is correct
13 Correct 1681 ms 760 KB Output is correct
14 Correct 1720 ms 804 KB Output is correct
15 Correct 1708 ms 640 KB Output is correct
16 Correct 1683 ms 760 KB Output is correct
17 Correct 1679 ms 760 KB Output is correct
18 Correct 1760 ms 672 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 384 KB Output is correct
2 Correct 300 ms 384 KB Output is correct
3 Correct 1917 ms 640 KB Output is correct
4 Correct 1945 ms 640 KB Output is correct
5 Correct 1954 ms 680 KB Output is correct
6 Correct 1807 ms 680 KB Output is correct
7 Correct 1849 ms 760 KB Output is correct
8 Correct 1940 ms 760 KB Output is correct
9 Correct 1877 ms 680 KB Output is correct
10 Correct 1730 ms 676 KB Output is correct
11 Correct 1700 ms 680 KB Output is correct
12 Correct 1698 ms 676 KB Output is correct
13 Correct 1681 ms 760 KB Output is correct
14 Correct 1720 ms 804 KB Output is correct
15 Correct 1708 ms 640 KB Output is correct
16 Correct 1683 ms 760 KB Output is correct
17 Correct 1679 ms 760 KB Output is correct
18 Correct 1760 ms 672 KB Output is correct
19 Execution timed out 9075 ms 1408 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 2048 KB Output is correct
2 Correct 45 ms 3576 KB Output is correct
3 Correct 84 ms 4860 KB Output is correct
4 Correct 83 ms 4984 KB Output is correct
5 Correct 88 ms 4988 KB Output is correct
6 Correct 83 ms 4856 KB Output is correct
7 Correct 89 ms 4852 KB Output is correct
8 Correct 101 ms 4856 KB Output is correct
9 Correct 100 ms 4856 KB Output is correct
10 Correct 73 ms 4856 KB Output is correct
11 Correct 78 ms 4860 KB Output is correct
12 Correct 73 ms 4856 KB Output is correct
13 Correct 70 ms 4856 KB Output is correct
14 Correct 67 ms 4856 KB Output is correct
15 Correct 67 ms 4856 KB Output is correct
16 Correct 60 ms 4760 KB Output is correct
17 Correct 62 ms 4856 KB Output is correct
18 Correct 70 ms 4856 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 384 KB Output is correct
2 Correct 300 ms 384 KB Output is correct
3 Correct 1917 ms 640 KB Output is correct
4 Correct 1945 ms 640 KB Output is correct
5 Correct 1954 ms 680 KB Output is correct
6 Correct 1807 ms 680 KB Output is correct
7 Correct 1849 ms 760 KB Output is correct
8 Correct 1940 ms 760 KB Output is correct
9 Correct 1877 ms 680 KB Output is correct
10 Correct 1730 ms 676 KB Output is correct
11 Correct 1700 ms 680 KB Output is correct
12 Correct 1698 ms 676 KB Output is correct
13 Correct 1681 ms 760 KB Output is correct
14 Correct 1720 ms 804 KB Output is correct
15 Correct 1708 ms 640 KB Output is correct
16 Correct 1683 ms 760 KB Output is correct
17 Correct 1679 ms 760 KB Output is correct
18 Correct 1760 ms 672 KB Output is correct
19 Execution timed out 9075 ms 1408 KB Time limit exceeded
20 Halted 0 ms 0 KB -