Submission #1044447

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044447		underwaterkillerwhale	Bubble Sort 2 (JOI18_bubblesort2)	C++17	0 / 100	13 ms	9688 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 = 1e6 + 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<pair<int,int>> vals;

struct Segment_Tree {
    int m;
    int st[N << 2];
    int lz[N << 2];

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

    void down (int id) {
        rep (i, id << 1, id << 1 | 1) {
            st[i] += 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;
            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] = max(st[id << 1], st[id << 1 | 1]);
    }

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

}ST;

int cps (pair<int,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, ++qr[i].fs;
    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], qr[i].fs++;

    rep (i, 1, n) vals.push_back({a[i], i});
    rep (i, 1, Q) vals.push_back(qr[i]);
    sort (ALL(vals));
    vals.resize(nval = unique(ALL(vals)) - vals.begin());
    rep (i, 1, n) a[i] = cps(MP(a[i], i));
    rep (i, 1, Q) qr[i].se = cps(MP(qr[i].se, qr[i].fs));
    ST.init(nval);
    rep (i, 1, n) {
        ST.update(a[i], a[i], i);
        ST.update (a[i], nval, -1);
    }
    vector<int> Ans;
    rep (i, 1, Q) {
        int p, val;
        tie(p, val) = qr[i];
        ST.update(a[p], a[p], -p);
        ST.update(a[p], nval, 1);
        ST.update(val, val, p);
        ST.update(val, nval, -1);
        a[p] = val;
        Ans.push_back(ST.st[1]);
//        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:107:1: warning: multi-line comment [-Wcomment]
  107 | //#define file(name) freopen(name".inp","r",stdin); \
      | ^
bubblesort2.cpp: In member function 'void Segment_Tree::update(int, int, int, int, int, int)':
bubblesort2.cpp:52:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |         int mid = l + r >> 1;
      |                   ~~^~~

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