Submission #160266

#	Time	Username	Problem	Language	Result	Execution time	Memory
160266		combi1k1	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	1989 ms	52948 KiB

bubblesort2

#include<bits/stdc++.h>

using namespace std;

#define X       first
#define Y       second
#define pb      push_back

#define FOR(i,a,b)      for(int i = a ; i < b ; ++i)

const int   N   = 1e6 + 1;
const int   inf = 1e9 + 1;

typedef pair<int,int>   ii;
typedef vector<int>     arr;

int tr[N << 1];
int lz[N << 1];

void app(int i,int v)   {
    tr[i] += v;
    lz[i] += v;
}
void upd(int l,int r,int v) {
    l += N - 1;
    r += N;
    int L = l;
    int R = r - 1;

    for(; l < r ; l >>= 1, r >>= 1) {
        if (l & 1)  app(l++,v);
        if (r & 1)  app(--r,v);
    }
    for(; L > 1 ; L >>= 1)  tr[L >> 1] = max(tr[L],tr[L ^ 1]) + lz[L >> 1];
    for(; R > 1 ; R >>= 1)  tr[R >> 1] = max(tr[R],tr[R ^ 1]) + lz[R >> 1];
}

arr countScans(arr a,arr p,arr x)   {
    int n = a.size();
    int q = p.size();

    vector<ii>  val;

    FOR(i,0,n)  val.pb(ii(a[i],i));
    FOR(i,0,q)  val.pb(ii(x[i],p[i]));

    sort(val.begin(),val.end());
    val.erase(unique(val.begin(),val.end()),val.end());

    int m = val.size();

    auto add = [&](int P)   {
        int p = lower_bound(val.begin(),val.end(),ii(a[P],P)) - val.begin() + 1;
        upd(p,m,-1);
        upd(p,p, P + 1);
    };
    auto rem = [&](int P)   {
        int p = lower_bound(val.begin(),val.end(),ii(a[P],P)) - val.begin() + 1;
        upd(p,m, 1);
        upd(p,p,-P - 1);
    };

    vector<int> res;

    FOR(i,0,n)  add(i);
    FOR(i,0,q)  {
        rem(p[i]);  a[p[i]] = x[i];
        add(p[i]);  res.push_back(tr[1]);
    }

    return  res;
}

/*int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    arr v = countScans({1,2,3,4},{0,2},{3,1});

    for(int x : v)  cout << x << " ";
}*/

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