Submission #747897

#	Time	Username	Problem	Language	Result	Execution time	Memory
747897		Sami_Massah	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	8702 ms	115224 KiB

bubblesort2

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


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

struct hash_pair {
    template <class T1, class T2>
    size_t operator()(const pair<T1, T2>& p) const
    {
        auto hash1 = hash<T1>{}(p.first);
        auto hash2 = hash<T2>{}(p.second);

        if (hash1 != hash2) {
            return hash1 ^ hash2;
        }

        // If hash1 == hash2, their XOR is zero.
          return hash1;
    }
};
unordered_map <pair<int, int>, int, hash_pair> cnv;
void make_tree(int l, int r, int ind){
    int mid = (l + r) / 2;
    L[ind] = l;
    R[ind] = r;
    if(l == r)
        return;
    make_tree(l, mid, ind * 2);
    make_tree(mid + 1, r, ind * 2 + 1);
}
void update_tree(int l, int r, int u, int k){
    if(r < L[u] || R[u] < l)
        return;
    if(l <= L[u] && R[u] <= r){
        num[u] += k;
        mx[u] += k;
        return;

    }
    update_tree(l, r, u * 2, k);
    update_tree(l, r, u * 2 + 1, k);
    mx[u] = max(mx[u * 2], mx[u * 2 + 1]) + num[u];
}
int get_max(int l, int r, int u){
    if(r < L[u] || R[u] < l)
        return 0;
    if(l <= L[u] && R[u] <= r)
        return mx[u];
    return max(get_max(l, r, u * 2), get_max(l, r, u * 2 + 1)) + num[u];
}
void set_tree(int l, int k){
    int x = get_max(l, l, 1);
    update_tree(l, l, 1, k - x);
}
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());
    int len = 1;
    for(auto i: pos)
        if(cnv[i] == 0){
            cnv[i] = len;
            len += 1;
        }
    make_tree(0, 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(get_max(0, len, 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