Submission #746499

#	Time	Username	Problem	Language	Result	Execution time	Memory
746499		nguyentunglam	Bubble Sort 2 (JOI18_bubblesort2)	C++17	60 / 100	153 ms	13632 KiB

bubblesort2

#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
using namespace std;
const int N = 1e5 + 01;
vector<ii> rrh;
int f[N], T[N << 2], lazy[N << 2];

void push(int s, int l, int r) {
    if (!lazy[s]) return;
    T[s] += lazy[s];
    if (l != r) {
        lazy[s << 1] += lazy[s];
        lazy[s << 1 | 1] += lazy[s];
    }
    lazy[s] = 0;
}

void up(int s, int l, int r, int from, int to, int val) {
    push(s, l, r);
    if (l > to || r < from) return;
    if (from <= l && r <= to) {
        lazy[s] += val;
        push(s, l, r);
        return;
    }
    int mid = l + r >> 1;
    up(s << 1, l, mid, from, to, val);
    up(s << 1 | 1, mid + 1, r, from, to, val);
    T[s] = max(T[s << 1], T[s << 1 | 1]);
}

int id(int pos, int val) {
    return upper_bound(rrh.begin(), rrh.end(), make_pair(val, pos)) - rrh.begin();
}

vector<int> countScans(vector<int> a, vector<int> pos, vector<int> val) {
    vector<int> ans(pos.size());
    int n = a.size();

    for(int i = 0; i < n; i++) rrh.emplace_back(a[i], i);
    for(int i = 0; i < pos.size(); i++) rrh.emplace_back(val[i], pos[i]);
    sort(rrh.begin(), rrh.end());
    rrh.resize(unique(rrh.begin(), rrh.end()) - rrh.begin());
    int m = rrh.size();

    for(int i = 0; i < n; i++) {
        int p = id(i, a[i]);
        up(1, 1, m, p, p, i + 1);
        up(1, 1, m, p, m, -1);
    }

    for(int i = 0; i < pos.size(); i++) {
        int p = id(pos[i], a[pos[i]]);
        up(1, 1, m, p, p, -pos[i] - 1);
        up(1, 1, m, p, m, 1);

        a[pos[i]] = val[i];
        p = id(pos[i], val[i]);
        up(1, 1, m, p, p, pos[i] + 1);
        up(1, 1, m, p, m, -1);
        ans[i] = T[1];
    }

    return ans;
}

#ifdef ngu
int main() {

    freopen ("task.inp", "r", stdin);
    freopen ("task.out", "w", stdout);

    int n, q; cin >> n >> q;
    vector<int> a(n), x(q), v(q);
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < q; i++) cin >> x[i] >> v[i];
    vector<int> ret = countScans(a, x, v);
    for(int &j : ret) cout << j << endl;
}
#endif // ngu

Compilation message (stderr)

bubblesort2.cpp: In function 'void up(int, int, int, int, int, int)':
bubblesort2.cpp:29:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |     int mid = l + r >> 1;
      |               ~~^~~
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:44:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int i = 0; i < pos.size(); i++) rrh.emplace_back(val[i], pos[i]);
      |                    ~~^~~~~~~~~~~~
bubblesort2.cpp:55:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for(int i = 0; i < pos.size(); i++) {
      |                    ~~^~~~~~~~~~~~

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