Submission #364511

#	Time	Username	Problem	Language	Result	Execution time	Memory
364511		buyolitsez	Bubble Sort 2 (JOI18_bubblesort2)	C++17	0 / 100	186 ms	6364 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>

using namespace std;

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")

#define eb emplace_back

typedef long long ll;

auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rnd(seed);


const int MAXN = 1e6 + 15;
const int ADD = 1e6;

int t[4 * MAXN], tadd[4 * MAXN];
int f[MAXN];

void Update(int pos, int val) {
    for(;pos < MAXN; pos = (pos | (pos + 1))) {
        f[pos] += val;
    }
}

int Sum(int pos) {
    int ans = 0;
    for(; pos >= 0; pos = (pos & (pos + 1)) - 1) {
        ans += f[pos];
    }
    return ans;
}

void Push(int v, int vl, int vr) {
    if (tadd[v]) {
        t[v] += tadd[v];
        if (vl != vr) {
            tadd[2 * v + 1] += tadd[v];
            tadd[2 * v + 2] += tadd[v];
        }
        tadd[v] = 0;
    }
}

void Update(int l, int r, int val, int v = 0, int vl = 0, int vr = MAXN - 1) {
    Push(v, vl, vr);
    if (vr < l || r < vl) {return;}
    if (vl >= l && vr <= r) {
        tadd[v] += val;
        Push(v, vl, vr);
        return;
    }
    int vm = vl + (vr - vl) / 2;
    Update(l, r, val, 2 * v + 1, vl, vm);
    Update(l, r, val, 2 * v + 2, vm + 1, vr);
    t[v] = max(t[2 * v + 1], t[2 * v + 2]);
}

int Query(int pos, int v = 0, int vl = 0, int vr = MAXN - 1) {
    Push(v, vl, vr);
    if (vl == vr) {
        return t[v];
    }
    int vm = vl + (vr - vl) / 2;
    if (pos <= vm) {
        return Query(pos, 2 * v + 1, vl, vm);
    }
    return Query(pos, 2 * v + 2, vm + 1, vr);
}

int GetMx() {
    Push(0, 0, MAXN - 1);
    return t[0];
}

std::vector<int> countScans(std::vector<int> aa,std::vector<int> xx,std::vector<int> vv){
    vector <ll> a, x, v, all;
    int n = aa.size(), q = xx.size();
    for (int i = 0; i < n; ++i) {
        a.eb(aa[i] * ADD + i);
        all.eb(a[i]);
    }
    for (int i = 0; i < xx.size(); ++i) {
        x.eb(xx[i]);
        v.eb(vv[i] * ADD + xx[i]);
        all.eb(v[i]);
    }
    sort(all.begin(), all.end());
    all.resize(unique(all.begin(), all.end()) - all.begin());
    for (int i = 0; i < n; ++i) {
        a[i] = lower_bound(all.begin(), all.end(), a[i]) - all.begin();
        Update(a[i], 1);
    }
    for (int i = 0; i < n; ++i) {
        Update(a[i], a[i], i);
        int cntLess = Sum(a[i] - 1);
        Update(a[i], a[i], -cntLess);
    }
    for (auto &u : v) {
        u = lower_bound(all.begin(), all.end(), u) - all.begin();
    }
    vector <int> s;
    for(int f = 0; f < q; ++f) {
        int pos = x[f];
        int x = a[pos];
        int y = v[f];
        a[pos] = y;
        Update(x, MAXN - 1, 1);
        Update(y, MAXN - 1, -1);
        Update(x, -1);
        Update(y, 1);
        int cntLess = Sum(y - 1);
        int nowVal = Query(y);
        Update(y, y, -nowVal + (pos - cntLess));
        s.eb(GetMx());
    }
    return s;
}

Compilation message (stderr)

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:87:23: 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 < xx.size(); ++i) {
      |                     ~~^~~~~~~~~~~

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