Submission #1043589

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043589		underwaterkillerwhale	Bubble Sort 2 (JOI18_bubblesort2)	C++17	39 / 100	70 ms	89044 KiB

bubblesort2

#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for (auto id : v)
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 5e5 + 7;
const int Mod = 1e9 + 7;
const int INF = 2e9;
const ll BASE = 137;

int n, nval, Q;
int a[N];
pair<int,int> qr[N];
vector<int> vals;
set<int,greater<int>> pos[(int)1e6 + 7];

struct Segment_Tree {
    struct Node {
        int val, fs;
        Node () : fs(0), val(0) {};
    };
    int m;
    Node st[((int)1e6 + 7) << 2];
    int lz[((int)1e6 + 7) << 2];

    void init (int n) {
        m = n;
    }

    void down (int id) {
        rep (i, id << 1, id << 1 | 1) {
            st[i].val += lz[id];
            lz[i] += lz[id];
        }
        lz[id] = 0;
    }

    void update (int id, int l, int r, int u, int v, int val) {
        if (l > v || r < u) return;
        if (l >= u && r <= v) {
            st[id].val += val;
            lz[id] += val;
            return;
        }
        int mid = l + r >> 1;
        down(id);
        update (id << 1, l, mid, u, v, val);
        update (id << 1 | 1, mid + 1, r, u, v, val);
        st[id].val = max(st[id << 1].val, st[id << 1 | 1].val);
    }

    void Assign (int id, int l, int r, int pos, int val) {
        if (l > pos || r < pos) return;
        if (l == r) {
            st[id].val += val - st[id].fs;
            st[id].fs = val;
            return;
        }
        int mid = l + r >> 1;
        down(id);
        Assign (id << 1, l, mid, pos, val);
        Assign (id << 1 | 1, mid + 1, r, pos, val);
        st[id].val = max(st[id << 1].val, st[id << 1 | 1].val);
    }

    void update (int u, int v, int val) {
        update (1, 1, m, u, v, val);
    }

    void Assign (int pos, int val) {
        Assign (1, 1, m, pos, val);
    }
}ST;

int cps (int x) {
    return lower_bound(ALL(vals), x) - vals.begin() + 1;
}

//void solution() {
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V) {
//    cin >> n;
//    rep (i, 1, n) cin >> a[i];
//    cin >> Q;
//    rep (i, 1, Q) cin >> qr[i].fs >> qr[i].se;
    n = SZ(A);
    Q = SZ(X);
    rep (i, 1, n) a[i] = A[i - 1];
    rep (i, 1, Q) qr[i].fs = X[i - 1], qr[i].se = V[i - 1];

    rep (i, 1, n) vals.push_back(qr[i].se);
    rep (i, 1, Q) vals.push_back(a[i]);
    sort (ALL(vals));
    vals.resize(nval = unique(ALL(vals)) - vals.begin());
    rep (i, 1, n) a[i] = cps(a[i]);
    rep (i, 1, Q) qr[i].se = cps(qr[i].se);
    ST.init(nval);
    rep (i, 1, n) {
        pos[a[i]].insert(i);
        ST.Assign(a[i], i);
        ST.update (a[i], nval, -1);
    }
    rep (i, 1, nval) pos[i].insert(0);
    vector<int> Ans;
    rep (i, 1, Q) {
        int p, val;
        tie(p, val) = qr[i];
        ++p;
        pos[a[p]].erase(p);
        pos[val].insert(p);
        ST.Assign(a[p], *pos[a[p]].begin());
        ST.update(a[p], nval, 1);
        ST.Assign(val, *pos[val].begin());
        ST.update(val, nval, -1);
        a[p] = val;
        Ans.push_back(ST.st[1].val);
//        cout << ST.st[1].val <<"\n";
    }
    return Ans;

}

//#define file(name) freopen(name".inp","r",stdin); \
//freopen(name".out","w",stdout);
//int main () {
////    file("c");
//    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
//    int num_Test = 1;
////    cin >> num_Test;
//    while (num_Test--)
//        solution();
//}
/*
no bug challenge +2
4
1 2 3 4
2
0 3
2 1
*/

Compilation message (stderr)

bubblesort2.cpp:134:1: warning: multi-line comment [-Wcomment]
  134 | //#define file(name) freopen(name".inp","r",stdin); \
      | ^
bubblesort2.cpp: In constructor 'Segment_Tree::Node::Node()':
bubblesort2.cpp:6:12: warning: 'Segment_Tree::Node::first' will be initialized after [-Wreorder]
    6 | #define fs first
      |            ^~~~~
bubblesort2.cpp:31:18: note: in expansion of macro 'fs'
   31 |         int val, fs;
      |                  ^~
bubblesort2.cpp:31:13: warning:   'int Segment_Tree::Node::val' [-Wreorder]
   31 |         int val, fs;
      |             ^~~
bubblesort2.cpp:32:9: warning:   when initialized here [-Wreorder]
   32 |         Node () : fs(0), val(0) {};
      |         ^~~~
bubblesort2.cpp: In member function 'void Segment_Tree::update(int, int, int, int, int, int)':
bubblesort2.cpp:57:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |         int mid = l + r >> 1;
      |                   ~~^~~
bubblesort2.cpp: In member function 'void Segment_Tree::Assign(int, int, int, int, int)':
bubblesort2.cpp:71:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |         int mid = l + r >> 1;
      |                   ~~^~~

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