Submission #747898

#	Time	Username	Problem	Language	Result	Execution time	Memory
747898		Sami_Massah	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	3778 ms	103132 KiB

bubblesort2

#include <bits/stdc++.h>
using namespace std;


const int maxn = 1e6 + 12, inf = 1e8;
int n, m, len, num[maxn * 4], mx[maxn * 4];
vector <int> ans;
vector <pair<int, int>> pos;
map <pair<int, int>, int> cnv;

void update_tree(int l, int r, int u, int k, int L = 0, int R = len){
    if(r < L || R < l)
        return;
    if(l <= L && R <= r){
        num[u] += k;
        mx[u] += k;
        return;

    }
    int mid = (L + R) / 2;
    update_tree(l, r, u * 2, k, L, mid);
    update_tree(l, r, u * 2 + 1, k, mid + 1, R);
    mx[u] = max(mx[u * 2], mx[u * 2 + 1]) + num[u];
}

vector <int> countScans(vector <int> a, vector <int> y, vector <int> x){
    n = a.size();
    m = x.size();
    for(int i = 0; i < m; i++)
        pos.push_back(make_pair(x[i], y[i]));
    for(int i = 0; i < n; i++)
        pos.push_back(make_pair(a[i], i));
    sort(pos.begin(), pos.end());
    len = 1;
    for(auto i: pos)
        if(cnv[i] == 0){
            cnv[i] = len;
            len += 1;
        }

    for(int i = 0; i < n; i++){
        int now = cnv[make_pair(a[i], i)];
        update_tree(now + 1, len, 1, -1);
        update_tree(now, now, 1, i);
     //   cout << now + 1 << ' ' << len << endl;
 //       cout << now << endl << endl;
    }
   // cout << get_max(0, len, 1) << endl;
   // cout << endl;
    for(int i = 0; i < m; i++){
        int now = cnv[make_pair(a[y[i]], y[i])];
        update_tree(now + 1, len, 1, 1);
        update_tree(now, now, 1, -y[i]);

        now = cnv[make_pair(x[i], y[i])];
        update_tree(now + 1, len, 1, -1);
        update_tree(now, now, 1, y[i]);

        a[y[i]] = x[i];
        ans.push_back(mx[1]);
    }
    return ans;


}
/*
int main(){
    vector <int> a, x, y;
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        int b;
        cin >> b;
        a.push_back(b);
    }
    for(int i = 0; i < m; i++){
        int b, c;
        cin >> b >> c;
        x.push_back(b);
        y.push_back(c);
    }
    countScans(a, x, y);
    for(int i: ans)
        cout << i << ' ';




}*/

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