Submission #421765

#	Time	Username	Problem	Language	Result	Execution time	Memory
421765		ACmachine	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	1832 ms	43584 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
#define FORD(i, j, k, l) for(int i = (j); i >= (k); i += (l))
#define REP(i, n) FOR(i, 0, n, 1)
#define REPD(i, n) FORD(i, n, 0, 1)
#define pb push_back
typedef long long ll;
const int INF = (int)1e9;
struct node{
    int lazy = 0;
    int max = 0;
    void apply(int l, int r, int val){
        lazy += val;
        max += val;
    }
};
struct segtree{
    node comb(const node& a, const node &b){
        node res;
        res.max = max(a.max, b.max);
        return res;
    }
    void push(int l, int r, int v){
        tree[v << 1].apply(l, r, tree[v].lazy);
        tree[v << 1 | 1].apply(l, r, tree[v].lazy);
        tree[v].lazy = 0;
    }
    int n;
    vector<node> tree;
    segtree(int _n){
        n = 1; 
        while(n < _n)
            n *= 2;
        tree.resize(2 * n);
    }
    node query(int l, int r){
        return query0(l, r, 0, n, 1);
    }
    node query0(int l, int r, int beg, int end, int v){
        if(beg >= l && end <= r)
            return tree[v];
        if(beg >= r || end <= l){
            node res;
            res.max = -INF;
            return res;
        }
        push(beg, end, v);
        int mid = (beg + end) >> 1;
        return comb(query0(l, r, beg, mid, v << 1), query0(l, r, mid, end, v << 1 | 1));
    }
    void upd(int l, int r, int val){
        upd0(l, r, 0, n, 1, val);
    }
    void upd0(int l, int r, int beg, int end, int v, int val){
        if(beg >= l && end <= r){
            tree[v].apply(beg, end, val);
            return;
        }
        if(beg >= r || end <= l)
            return;
        push(beg, end, v);
        int mid = (beg + end) >> 1;
        upd0(l, r, beg, mid, v << 1, val);
        upd0(l, r, mid, end, v << 1 | 1, val);
        tree[v] = comb(tree[v << 1], tree[v << 1 | 1]);
    }
};
vector<int> countScans(vector<int> a,vector<int> x,vector<int> v){
    int q = x.size();
    int n = a.size();
    vector<int> res(q);
	vector<array<int, 3>> comp;
    REP(i, n){
        comp.pb({a[i], i, -1});
    }
    REP(i, q){
        comp.pb({v[i], x[i], i});
    }
    sort(comp.begin(), comp.end());
    // values compressed; if they were equal initially, they are tiebreaked using index; if index > .., compression value is bigger
    REP(i, comp.size()){
        auto y = comp[i];
        if(y[2] == -1){ // in intiail array
            a[y[1]] = i;
        }
        else{
            v[y[2]] = i;
        }
    }
    segtree st(comp.size() + 10);
    st.upd(0, st.n, -INF);
    REP(i, n){
        st.upd(a[i], a[i] + 1, INF + i);
        st.upd(a[i] + 1, st.n, -1);
    }
    REP(i, q){
        int id = x[i];
        st.upd(a[id], a[id] + 1, -INF - id);
        st.upd(a[id] + 1, st.n, 1);
        a[id] = v[i];
        st.upd(a[id], a[id] + 1, INF + id);
        st.upd(a[id] + 1, st.n, -1);
        auto no = st.query(0, st.n);
        res[i] = no.max;
    }
	return res;
}

Compilation message (stderr)

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:4:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
      |                                            ^
bubblesort2.cpp:6:19: note: in expansion of macro 'FOR'
    6 | #define REP(i, n) FOR(i, 0, n, 1)
      |                   ^~~
bubblesort2.cpp:83:5: note: in expansion of macro 'REP'
   83 |     REP(i, comp.size()){
      |     ^~~

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