Submission #224816

#	Time	Username	Problem	Language	Result	Execution time	Memory
224816		Bruteforceman	Bubble Sort 2 (JOI18_bubblesort2)	C++11	100 / 100	4777 ms	230776 KiB

bubblesort2

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

void pushdown(int c) {
    if(!prop[c]) return ;
    int l = c << 1;
    int r = l + 1;
    t[l] += prop[c]; t[r] += prop[c];
    prop[l] += prop[c]; prop[r] += prop[c];
    prop[c] = 0;
}
void add(int x, int y, int val, int c = 1, int b = 1, int e = idx) {
    if(x <= b && e <= y) {
        t[c] += val;
        prop[c] += val;
        return ;
    }
    if(y < b || e < x) return ;
    pushdown(c);
    int m = (b + e) >> 1;
    int l = c << 1;
    int r = l + 1;
    add(x, y, val, l, b, m);
    add(x, y, val, r, m + 1, e);
    t[c] = max(t[l], t[r]);
}
inline int getMin() {
    return max(0, t[1]);
}
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] = opt[idx] = 0;
        cont[idx].clear();
    }
    for(int i = 1; i <= idx * 4; i++) {
        t[i] = prop[i] = 0;
    }
    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];
        add(i, 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 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:38:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < A.size(); i++) cmp[A[i]];
                    ~~^~~~~~~~~~
bubblesort2.cpp:39:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < V.size(); i++) cmp[V[i]];
                    ~~^~~~~~~~~~
bubblesort2.cpp:49:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < A.size(); i++) {
                    ~~^~~~~~~~~~
bubblesort2.cpp:60: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: 40 / 40