Submission #552608

#	Time	Username	Problem	Language	Result	Execution time	Memory
552608		RaresFelix	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	3970 ms	132372 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
#define MN 1000071
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
int n, q, ma_val;

struct nod {
    int mi, ma, nr_activ;
    int lazy;
} V[4 * MN];

void prop(int u, int s, int d) {
    V[u].mi += V[u].lazy;
    V[u].ma += V[u].lazy;
    if(s != d) {
        V[u << 1].lazy += V[u].lazy;
        V[u << 1 | 1].lazy += V[u].lazy;
    }
    V[u].lazy = 0;
}

void update_range(int l, int r, int v, int u = 1, int s = 1, int d = ma_val) {
    if(r < s || d < l) return;
    prop(u, s, d);
    if(l <= s && d <= r) {
        V[u].lazy = v;
        prop(u, s, d);
        return;
    }
    update_range(l, r, v, u << 1, s, (s + d) >> 1);
    update_range(l, r, v, u << 1 | 1, ((s + d) >> 1) + 1, d);
    V[u].mi = min(V[u << 1].mi, V[u << 1 | 1].mi);
    V[u].ma = max(V[u << 1].ma, V[u << 1 | 1].ma);
}

void init(int u = 1, int s = 1, int d = ma_val) {
    if(s != d) {
        init(u << 1, s, (s + d) >> 1);
        init(u << 1 | 1, ((s + d) >> 1) + 1, d);
    }
    V[u].ma = V[u].nr_activ = V[u].lazy = 0;
    V[u].mi = INT_MAX;
}

void update_active(int p, int v, int u = 1, int s = 1, int d = ma_val) {
    prop(u, s, d);
    if(d < p || p < s) return;
    if(s == d) {
        V[u].nr_activ = v;
        if(!V[u].nr_activ) V[u].ma = V[u].lazy = 0, V[u].mi = INT_MAX;
        return;
    }
    update_active(p, v, u << 1, s, (s + d) >> 1);
    update_active(p, v, u << 1 | 1, ((s + d) >> 1) + 1, d);
    V[u].nr_activ = V[u << 1].nr_activ + V[u << 1 | 1].nr_activ;
    V[u].mi = min(V[u << 1].mi, V[u << 1 | 1].mi);
    V[u].ma = max(V[u << 1].ma, V[u << 1 | 1].ma);
    if(!V[u].nr_activ) V[u].ma = V[u].lazy = 0, V[u].mi = INT_MAX;
}

int query_smaller(int p, int u = 1, int s = 1, int d = ma_val) {
    prop(u, s, d);
    if(p <= s) return 0;
    if(d < p) return V[u].nr_activ;
    return query_smaller(p, u << 1, s, (s + d) >> 1) + query_smaller(p, u << 1 | 1, ((s + d) >> 1) + 1, d);
}

void update_val(int p, int v, int u = 1, int s = 1, int d = ma_val) {
    prop(u, s, d);
    if(p < s || d < p) return;
    if(s == d) {
        V[u].ma = V[u].mi = v;
        return;
    }
    update_val(p, v, u << 1, s, (s + d) >> 1);
    update_val(p, v, u << 1 | 1, ((s + d) >> 1) + 1, d);
    V[u].mi = min(V[u << 1].mi, V[u << 1 | 1].mi);
    V[u].ma = max(V[u << 1].ma, V[u << 1 | 1].ma);
}

int brute(vector<int> A) {
    int re = 0, ok;
    do {
        ok = 0;
        for(int i = 0; i < A.size() - 1; ++i)
            if(A[i] > A[i + 1]) swap(A[i], A[i + 1]), ok = 1;
        re += ok;
    } while (ok);
    return re;
}

vector<int> countScans(vector<int> A,vector<int> X,vector<int> VQ){
    n = A.size(), q = X.size();
    vector<pair<int, int> > Ord;
    map<pair<int, int>, int> MNorm;
    for(int i = 0; i < n; ++i) Ord.push_back({A[i], i});
    for(int i = 0; i < q; ++i)
        Ord.push_back({VQ[i], X[i]});
    sort(Ord.begin(), Ord.end());
    for(int i = 0; i < Ord.size(); ++i) MNorm[Ord[i]] = i + 1;
    for(int i = 0; i < n; ++i) A[i] = MNorm[{A[i], i}];
    for(int i = 0; i < q; ++i) VQ[i] = MNorm[{VQ[i], X[i]}];
    ma_val = Ord.size();
    init();
    for(int i = 0; i < n; ++i)
        update_active(A[i], 1);
    for(int i = 0; i < n; ++i)
        update_val(A[i], i - query_smaller(A[i]));
    vector<int> answer;
    for(int i = 0; i < q; ++i) {
        int poz = X[i], val = VQ[i];
        update_active(A[poz], 0);
        update_range(A[poz] + 1, ma_val, 1);
        A[poz] = val;
        update_active(A[poz], 1);
        update_val(A[poz], poz - query_smaller(A[poz]));
        update_range(A[poz] + 1, ma_val, -1);
        answer.push_back(V[1].ma);
    }
    return answer;
}

Compilation message (stderr)

bubblesort2.cpp: In function 'int brute(std::vector<int>)':
bubblesort2.cpp:87:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for(int i = 0; i < A.size() - 1; ++i)
      |                        ~~^~~~~~~~~~~~~~
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:102:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for(int i = 0; i < Ord.size(); ++i) MNorm[Ord[i]] = i + 1;
      |                    ~~^~~~~~~~~~~~

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