Submission #224813

#	Time	Username	Problem	Language	Result	Execution time	Memory
224813		Bruteforceman	Bubble Sort 2 (JOI18_bubblesort2)	C++11	60 / 100	9030 ms	93944 KiB

bubblesort2

#include "bits/stdc++.h"
#include "bubblesort2.h"
using namespace std;
const int maxn = 1000010;
int t[maxn], opt[maxn], pre[maxn];
set <int> cont[maxn];
int idx;

int solve(vector <int> &A) {
    vector <int> cmp (A.size()), pos (A.size());
    for(int i = 0; i < A.size(); i++) cmp[i] = i;
    stable_sort(cmp.begin(), cmp.end(), [&] (int i, int j) { return A[i] < A[j]; });
    for(int i = 0; i < A.size(); i++) pos[cmp[i]] = i;
    int ans = 0;
    for(int i = 0; i < A.size(); i++) {
        ans = max(ans, i - pos[i]);
    }
    return ans;
}

void add(int l, int r, int x) {
    for(int i = l; i <= r; i++) {
        t[i] += x;
    }
}
int getMin() {
    int ans = 0;
    for(int i = 1; i <= idx; i++) {
        ans = max(ans, t[i]);
    }
    return ans;
}

std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
    vector <int> answer (X.size());
    map <int, int> cmp;
    for(int i = 0; i < A.size(); i++) cmp[A[i]];
    for(int i = 0; i < V.size(); i++) cmp[V[i]];
    idx = 0;
    for(auto &i : cmp) {
        i.second = ++idx;
        pre[idx] = t[idx] = opt[idx] = 0;
        cont[idx].clear();
    }
    for(int i = 0; i < A.size(); i++) {
        A[i] = cmp[A[i]];
        pre[A[i]] += 1;
        opt[A[i]] = i + 1;
        cont[A[i]].insert(i + 1);
    }
    for(int i = 1; i <= idx; i++) {
        pre[i] += pre[i - 1];
        t[i] = opt[i] - pre[i];
        cont[i].insert(0);
    }
    for(int i = 0; i < V.size(); i++) {
        int x = X[i];
        int tmp;
        V[i] = cmp[V[i]];

        add(A[x], idx, 1);
        cont[A[x]].erase(x + 1);
        tmp = opt[A[x]];
        opt[A[x]] = *cont[A[x]].rbegin();
        add(A[x], A[x], opt[A[x]] - tmp);


        A[x] = V[i];
        add(A[x], idx, -1);
        cont[A[x]].insert(x + 1);
        tmp = opt[A[x]];
        opt[A[x]] = *cont[A[x]].rbegin();
        add(A[x], A[x], opt[A[x]] - tmp);
        answer[i] = getMin();
    }
    return answer;
}

Compilation message (stderr)

bubblesort2.cpp: In function 'int solve(std::vector<int>&)':
bubblesort2.cpp:11:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < A.size(); i++) cmp[i] = i;
                    ~~^~~~~~~~~~
bubblesort2.cpp:13:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < A.size(); i++) pos[cmp[i]] = i;
                    ~~^~~~~~~~~~
bubblesort2.cpp:15:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < A.size(); i++) {
                    ~~^~~~~~~~~~
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:37:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < A.size(); i++) cmp[A[i]];
                    ~~^~~~~~~~~~
bubblesort2.cpp:38:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < V.size(); i++) cmp[V[i]];
                    ~~^~~~~~~~~~
bubblesort2.cpp:45:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < A.size(); i++) {
                    ~~^~~~~~~~~~
bubblesort2.cpp:56:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < V.size(); i++) {
                    ~~^~~~~~~~~~

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