Submission #767988

#	Time	Username	Problem	Language	Result	Execution time	Memory
767988		phoenix	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	2206 ms	75416 KiB

bubblesort2

#include<bits/stdc++.h>

using namespace std;

const int inf = 1e9;

const int N = (1 << 20);
int cnt[2 * N];
int add[2 * N];
vector<int> maxf(2 * N, -inf);
int lb[2 * N];
int rb[2 * N];

void build(int v = 1, int l = 0, int r = N - 1) {
    lb[v] = l;
    rb[v] = r;
    if(l == r) {
        return;
    }
    int m = (l + r) / 2;
    build(2 * v, l, m);
    build(2 * v + 1, m + 1, r);
}

void setpush(int v, int x) {
    maxf[v] += x;
    add[v] += x;
}
void push(int v) {
    if(!add[v] || lb[v] == rb[v]) return;
    setpush(2 * v, add[v]);
    setpush(2 * v + 1, add[v]);
    add[v] = 0;
}
void update(int ql, int qr, int x, int v = 1) {
    if(rb[v] < ql || lb[v] > qr) 
        return;
    if(ql <= lb[v] && rb[v] <= qr) {
        setpush(v, x);    
        return;
    }
    push(v);
    update(ql, qr, x, 2 * v);
    update(ql, qr, x, 2 * v + 1);
    cnt[v] = cnt[2 * v] + cnt[2 * v + 1];
    maxf[v] = max(maxf[2 * v], maxf[2 * v + 1]);
}

int get_cnt(int ql, int qr, int v = 1) {
    if(ql > qr || rb[v] < ql || lb[v] > qr) 
        return 0;
    if(ql <= lb[v] && rb[v] <= qr) 
        return cnt[v];
    push(v);
    return get_cnt(ql, qr, 2 * v) + get_cnt(ql, qr, 2 * v + 1);
}
void change(int pos, int x, int y, int v = 1) {
    if(rb[v] < pos || lb[v] > pos) 
        return;
    if(lb[v] == rb[v]) {
        cnt[v] = x;
        maxf[v] = y; 
        return;
    }
    push(v);
    change(pos, x, y, 2 * v);
    change(pos, x, y, 2 * v + 1);
    cnt[v] = cnt[v * 2] + cnt[2 * v + 1];
    maxf[v] = max(maxf[2 * v], maxf[2 * v + 1]);
}
void insert(int pos, int val) {
    change(pos, 1, val - get_cnt(0, pos - 1));
    update(pos + 1, N - 1, -1);
}
void erase(int pos) {
    change(pos, 0, -inf);
    update(pos + 1, N - 1, +1);
}


int find(vector<pair<int, int>> &v, pair<int, int> x) {

    int l = -1, r = (int)v.size();
    while(r - l > 1) {
        int m = (l + r) / 2;
        if(v[m] < x) l = m;
        else r = m;
    }
    if(r == (int)v.size() || v[r] != x) return -1;
    return r;
}

int n, q;
void compress(vector<int> &a, vector<pair<int, int>> &b) {
    int n = (int)a.size();
    vector<pair<int, int>> mp;
    for(int i = 0; i < n; i++) {
        mp.push_back(make_pair(a[i], i));
    }
    for(auto g : b) 
        mp.push_back(g);
    sort(mp.begin(), mp.end());

    int m = (int)mp.size();
    int w[m];
    int k = 0;
    for(int i = 0; i < m; i++) {
        if(i && mp[i] != mp[i - 1]) 
            w[i] = ++k;
        else w[i] = k;
    } 
    for(int i = 0; i < n; i++) {
        a[i] = w[find(mp, make_pair(a[i], i))];
    }
    for(auto &g : b) {
        g.first = w[find(mp, g)];
    }
    mp.clear();
}



vector<int> countScans(vector<int> a, vector<int> X, vector<int> V) {
    build();
    n = (int)a.size();
    q = (int)X.size();
    vector<int> res(q);
    vector<pair<int, int>> updates;
    for(int i = 0; i < q; i++) 
        updates.push_back({V[i], X[i]});
    compress(a, updates);
    for(int i = 0; i < n; i++) {
        insert(a[i], i);
    }
    for(int i = 0; i < q; i++) {
        int pos = updates[i].second, val = updates[i].first;
        erase(a[pos]);
        insert(val, pos);
        // if(a[pos] < val) update(a[pos] + 1, val, +1);
        // else update(val + 1, a[pos], -1);
        a[pos] = val;
        
        res[i] = maxf[1];
    }
    return res;
}

    

// int main() {
//     ios::sync_with_stdio(0);
//     cin.tie(0);cout.tie(0);
//     int n, q;
//     cin >> n >> q;
//     vector<int> A(n);
//     vector<int> X(q);
//     vector<int> 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> res = countScans(A, X, V);
//     for(int c : res) 
//         cout << c << '\n'; 
// }

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