Submission #1269335

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269335		yhx3	Bubble Sort 2 (JOI18_bubblesort2)	C++20	38 / 100	327 ms	1076 KiB

bubblesort2

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// #define int long long
#define rep(i,a,b) for (int i = a; i < b; i++)
#define rrep(i,a,b) for (int i = a; i >= b; i--)
void N() {cout<<"NO\n";}
void Y() {cout<<"YES\n";}
void isTrue(bool ope) {if (ope) Y();else N();}
int pw(int x,int t) {int res = 1;while (t--) res *= x;return res;}
int lg(int x,int b) {int res = 0;while (x >= b) {x/=b;res++;}return res;}
int MD = 1e9+7;
// int MX_VL = 1e18;
int MX_ll = 2e9;

vector<int> countScans(vector<int> a,vector<int> x,vector<int> v) {
    vector<int> ans;
    int mx = 0;
    ordered_set<int> st;
    vector<int> m(a.size());
    m[0] = 0;
    int idx = 0;
    st.insert(a[0]);
    rep(i,1,a.size()) {
        int x = st.size()-st.order_of_key(a[i]);
        if (x > mx) idx = i;
        mx = max(mx,x);
        m[i] = x;
        st.insert(a[i]);
    }
    int res = mx;
    int n = a.size();
    rep(t,0,x.size()) {
        if (v[t] > a[x[t]]) {
            rep(i,x[t]+1,n) {
                if (a[i] >= a[x[t]] && a[i] < v[t]) {
                    m[i]++;
                }
            }
            rep(i,0,x[t]) {
                if (a[i] > a[x[t]] && a[i] <= v[t]) m[x[t]]--;
            }
            res = *max_element(m.begin(),m.end());
            ans.push_back(res);
        } else if (v[t] < a[x[t]]) {
            if (idx > x[t]) res = 0;
            rep(i,x[t]+1,n) {
                if (a[i] < a[x[t]] && a[i] >= v[t]) {
                    m[i]--;
                }
            }
            rep(i,0,x[t]) {
                if (a[i] <= a[x[t]] && a[i] > v[t]) m[x[t]]++;
            }
            res = *max_element(m.begin(),m.end());
            ans.push_back(res);
        } else ans.push_back(res);
        a[x[t]] = v[t];
    }
    return ans;
}
//
// void solve() {
//
// }
//
// signed main() {
//     ios_base::sync_with_stdio(false);
//     cin.tie(nullptr);
// }

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