Submission #462286

#	Time	Username	Problem	Language	Result	Execution time	Memory
462286		Killer2501	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	2996 ms	153208 KiB

bubblesort2

#include <bits/stdc++.h>
using namespace std;
#define ll int
#define pll pair<ll, ll>
#define fi first
#define se second
#define pb push_back

const int N = 1e6+5;
const ll mod = 998244353;
const int base = 300;

ll m, n, t, k, d[N], a[N], b[N], c[N], ans, tong, st[N*4], lazy[N*4], fe[N], sz;
vector<pll> adj[N];
vector<ll> kq;
ll pw(ll k, ll n)
{
    ll total = 1;
    for(; n; n >>= 1)
    {
        if(n & 1)total = total * k % mod;
        k = k * k % mod;
    }
    return total;
}
ll lwr(ll x)
{
    return lower_bound(kq.begin(), kq.end(), x) - kq.begin() + 1;
}
string s;
void add(ll id, ll x)
{
    for(; id <= sz; id += id & -id)fe[id] += x;
}
ll get(ll id)
{
    ll total = 0;
    for(; id; id -= id & -id)total += fe[id];
    return total;
}
set<ll> val[N];
void down(ll id)
{
    if(!lazy[id])return;
    st[id*2] += lazy[id];
    st[id*2+1] += lazy[id];
    lazy[id*2] += lazy[id];
    lazy[id*2+1] += lazy[id];
    lazy[id] = 0;
}
void update(ll id, ll l, ll r, ll u, ll v, ll x)
{
    if(u <= l && r <= v)
    {
        if(u == v)st[id] = x;
        else
        {
            st[id] += x;
            lazy[id] += x;
        }
        return;
    }
    if(u > v || u > r || l > v)return;
    ll mid = (l + r) / 2;
    down(id);
    update(id*2, l, mid, u, v, x);
    update(id*2+1, mid+1, r, u, v, x);
    st[id] = max(st[id*2], st[id*2+1]);
}
void cal(ll x)
{
    if(val[x].empty())update(1, 1, sz, x, x, -mod);
    else
    {
        k = (*val[x].rbegin()) - get(x);
        update(1, 1, sz, x, x, k);
    }
}
vector<ll> countScans(vector<ll> A, vector<ll> X, vector<ll> V)
{
    //cin >> n >> m;
    n = A.size();
    m = X.size();
    for(int i = 1; i <= n; i ++)
    {
        a[i] = A[i-1];
        //cin >> a[i];
        kq.pb(a[i]);
    }
    for(int i = 1; i <= m; i ++)
    {
        b[i] = X[i-1] + 1;
        c[i] = V[i-1];
        //cin >> b[i] >> c[i];
        kq.pb(c[i]);
    }
    sort(kq.begin(), kq.end());
    kq.erase(unique(kq.begin(), kq.end()), kq.end());
    sz = kq.size();
    for(int i = 1; i <= n; i ++)
    {
        a[i] = lwr(a[i]);
        add(a[i], 1);
        val[a[i]].insert(i);
    }
    for(int i = 1; i <= m; i ++)c[i] = lwr(c[i]);
    for(int i = 1; i <= n; i ++)
    {
        k = (*val[a[i]].rbegin()) - get(a[i]);
        update(1, 1, sz, a[i], a[i], k);
    }
    vector<ll> res;
    for(int i = 1; i <= m; i ++)
    {
        val[a[b[i]]].erase(b[i]);
        val[c[i]].insert(b[i]);
        add(a[b[i]], -1);
        add(c[i], 1);
        update(1, 1, sz, a[b[i]]+1, sz, 1);
        update(1, 1, sz, c[i]+1, sz, -1);
        cal(a[b[i]]);
        cal(c[i]);
        a[b[i]] = c[i];
        //cout << st[1] << '\n';
        res.pb(st[1]);
    }
    return res;
}

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