Submission #1216149

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216149		sitingfake	Bubble Sort 2 (JOI18_bubblesort2)	C++20	100 / 100	1373 ms	43956 KiB

bubblesort2

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

#define execute cerr << " Time: " << fixed << setprecision(6) << (1.0 * clock() / CLOCKS_PER_SEC) << "s\n";
#define ll long long
#define ld double
#define ii pair<int,int>
#define se second
#define fi first
#define iii pair<int,ii>
#define all(v) v.begin(),v.end()
#define bit(x,i) (((x)>>(i))&1LL)
#define flip(x,i) ((x)^(1LL<<(i)))
#define ms(d,x) memset(d,x,sizeof(d))
#define sitingfake 1
#define orz 1

//constant

const ll mod = 1e9 + 7;
const long long linf = 4557430888798830399;
const int inf = 1061109567;
const int maxarr = 1e6 + 5;
const int dx[] = {0,1,-1,0};
const int dy[] = {1,0,0,-1};

template<typename T> bool maximize(T &a, const T &b)
{
    if(a < b) {a = b; return 1;}
    return 0;
}

template<typename T> bool minimize(T &a, const T &b)
{
    if(a > b) {a = b; return 1;}
    return 0;
}

inline void Plus(ll & a ,ll b)
{
    b %= mod;
    a += b;
    if(a >= mod) a -= mod;
    if(a < 0) a += mod;
    return;
}

inline void Mul(ll & a, ll b)
{
    a %= mod; b %= mod;
    a *= b;
    a %= mod;
    return;
}

//code

const int maxn = 5e5 + 7;

int a[maxn];

int lazy[8 * maxn] , st[8 * maxn];

int bit[2 * maxn];

int Lim;

int n , q;

void up(int x , int val)
{
    for(; x <= Lim; x += (x & -x))
    {
        bit[x] += val;
    }
}

int get(int x)
{
    int ans = 0;
    for(; x > 0; x -= (x & -x))
    {
        ans += bit[x];
    }
    return ans;
}

void Apply(int i ,int val)
{
    st[i] += val;
    lazy[i] += val;
}

void Push(int i)
{
    if(lazy[i])
    {
        Apply(i * 2 , lazy[i]);
        Apply(i * 2 + 1, lazy[i]);
        lazy[i] = 0;
    }
}
void UpdatePos(int i ,int l,int r, int pos , int val)
{
    if(pos >r || pos < l) return;
    if(l == r)
    {
        st[i] = val;
        return;
    }

    int mid = (r + l) >> 1;

    Push(i);

    UpdatePos(i * 2 , l , mid , pos , val);
    UpdatePos(i * 2 + 1, mid + 1 , r , pos , val);

    st[i] = max(st[i * 2] , st[i * 2 + 1]);
}

void UpdateRange(int i ,int l ,int r, int u , int v , int val)
{
    if(u > r || v < l) return;
    if(u <= l && r <= v)
    {
        st[i] += val;
        lazy[i] += val;
        return;
    }

    int mid = (r + l) >> 1;

    Push(i);

    UpdateRange(i * 2, l , mid , u , v , val);
    UpdateRange(i * 2 + 1 , mid + 1 , r , u , v, val);
    st[i] = max(st[i * 2] , st[i * 2 + 1]);
}

void Reform(vector <int> &a , vector <int> &x , vector <int> &v)
{
    vector <ii> P;

    for(int i = 0; i < n ; i++) P.push_back(ii(a[i] , i));
    for(int i = 0; i < q ; i++) P.push_back(ii(v[i] , x[i]));

    sort(all(P));
    P.resize(unique(all(P)) - P.begin());

    for(int i = 0; i < n ; i++)
    {
        a[i] = lower_bound(all(P) , ii(a[i] , i)) - P.begin() + 1;
    }

    for(int i = 0; i < q ; i++)
    {
        v[i] = lower_bound(all(P) , ii(v[i] , x[i])) - P.begin() + 1;
    }

    Lim = P.size();
}

vector <int> countScans(vector <int> a , vector <int> x , vector <int> v)
{
    n = a.size();
    q = x.size();

    vector <int> ans;

    Reform(a ,x , v);

    for(int i = 0; i < n; i++)
    {
        up(a[i] , 1);
    }

    ms(st , -0x3f);

    for(int i = 0; i < n; i++)
    {
        UpdatePos(1 , 1, Lim , a[i] , i - get(a[i] - 1));
    }

    for(int i = 0; i < q; i++)
    {
        int Old = a[x[i]] , New = v[i];

        if(Old == New)
        {
            ans.push_back(st[1]);
            continue;
        }

        up(Old , -1);
        up(New , 1);

        UpdatePos(1 , 1, Lim , Old , -inf);
        UpdatePos(1 , 1, Lim , New , x[i] - get(New - 1));

        if(Old + 1 < New)
        {
            UpdateRange(1 , 1 , Lim , Old + 1, New - 1 , 1);// -(-1)
        }
        else if(New + 1 < Old)
        {
            UpdateRange(1 , 1, Lim , New + 1, Old - 1 , -1);
        }

        ans.push_back(st[1]);
        a[x[i]] = New;
    }

    return ans;
}


//void solve(void)
//{
//    int n , q;
//    cin >> n >> q;
//    vector <int> a;
//    for(int i = 1; i <= n; i++)
//    {
//        int x;cin >>x;
//        a.push_back(x);
//    }
//
//    vector <int> x(q) , v(q);
//
//    for(int i = 0; i < q; i ++) cin >> x[i] >> v[i];
//
//    vector <int> ans = countScans(a , x, v);
//    for(int i : ans) cout << i << "\n";
//}
/**
//4 2
//1 2 3 4
//0 3
//2 1
**/
//signed main()
//{
//   ios_base::sync_with_stdio(0);
//   cin.tie(0);
//   cout.tie(0);
//
//   #define task ""
//
//   if(fopen(task".inp","r"))
//   {
//       freopen(task".inp","r",stdin);
//       freopen(task".out","w",stdout);
//   }
//
//   int tc; tc = 1;
//
//   while(tc--) solve();
//
//   //execute;
//}

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