Submission #1297425

#	Time	Username	Problem	Language	Result	Execution time	Memory
1297425		danglayloi1	Bubble Sort 2 (JOI18_bubblesort2)	C++20	100 / 100	1457 ms	157816 KiB

bubblesort2

#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f
using namespace std;
using ll = long long;
const ll mod=1e9+7;
const int nx=1e6+5;
set<int> pos[nx];
int nod[nx<<2], la[nx<<2], pre[nx];
void build(int id, int l, int r)
{
    la[id]=0;
    if(l==r) return void(nod[id]=*pos[l].rbegin()-pre[l]);
    int mid=(l+r)>>1;
    build(id<<1, l, mid);
    build(id<<1|1, mid+1, r);
    nod[id]=max(nod[id<<1], nod[id<<1|1]);
}
void down(int id)
{
    if(!la[id]) return;
    for(int j = id*2; j <= id*2+1; j++)
        la[j]+=la[id], nod[j]+=la[id];
    la[id]=0;
}
void update(int id, int l, int r, int u, int v, int val)
{
    if(l>v || r<u) return;
    if(l>=u && r<=v)
    {
        nod[id]+=val;
        la[id]+=val;
        return;
    }
    int mid=(l+r)>>1;
    down(id);
    update(id<<1, l, mid, u, v, val);
    update(id<<1|1, mid+1, r, u, v, val);
    nod[id]=max(nod[id<<1], nod[id<<1|1]);
}
int get(int id, int l, int r, int u, int v)
{
    if(l>v || r<u) return -inf;
    if(l>=u && r<=v) return nod[id];
    int mid=(l+r)>>1;
    down(id);
    return max(get(id<<1, l, mid, u, v), get(id<<1|1, mid+1, r, u, v));
}
vector<int> countScans(vector<int> a, vector<int> X, vector<int> V)
{
    vector<int> rar;
    rar.clear();
    int n=a.size();
    for(int i = 0; i < n; i++)
        rar.emplace_back(a[i]);
    int q=X.size();
    for(int i = 0; i < q; i++)
        rar.emplace_back(V[i]);
    sort(rar.begin(), rar.end());
    rar.erase(unique(rar.begin(), rar.end()), rar.end());
    int m=rar.size();
    pre[0]=0;
    for(int i = 1; i <= m; i++)
        pos[i].emplace(-inf), pre[i]=0;
    for(int i = 0; i < n; i++)
    {
        a[i]=upper_bound(rar.begin(), rar.end(), a[i])-rar.begin();
        pos[a[i]].emplace(i);
        pre[a[i]]++;
    }
    for(int i = 1; i <= m; i++)
        pre[i]+=pre[i-1];
    build(1, 1, m);
    vector<int> res;
    res.clear();
    // for(int j = 1; j <= m; j++)
    //         cout<<get(1, 1, m, j, j)<<' ';
    //     cout<<'\n';
    for(int i = 0; i < q; i++)
    {
        int old=*pos[a[X[i]]].rbegin();
        pos[a[X[i]]].erase(pos[a[X[i]]].find(X[i]));
        int nw=*pos[a[X[i]]].rbegin();
        update(1, 1, m, a[X[i]], a[X[i]], nw-old);
        update(1, 1, m, a[X[i]], m, 1);
        int val=upper_bound(rar.begin(), rar.end(), V[i])-rar.begin();
        old=*pos[val].rbegin();
        pos[val].emplace(X[i]);
        nw=*pos[val].rbegin();
        update(1, 1, m, val, val, nw-old);
        update(1, 1, m, val, m, -1);
        a[X[i]]=val;
        res.emplace_back(nod[1]+1);
        // for(int j = 1; j <= m; j++)
        //     cout<<get(1, 1, m, j, j)<<' ';
        // cout<<'\n';
    }
    return res;
}
// signed main()
// {
//     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//     freopen("inputf.in", "r", stdin);
//     freopen("outputf.out", "w", stdout);
//     int n, q;
//     cin>>n>>q;
//     vector<int> a, x, v;
//     a.clear(), x.clear(), v.clear();
//     for(int i = 0; i < n; i++)
//     {
//         int p;
//         cin>>p;
//         a.emplace_back(p);
//     }
//     for(int i = 0; i < q; i++)
//     {
//         int l, r;
//         cin>>l>>r;
//         x.emplace_back(l);
//         v.emplace_back(r);
//     }
//     vector<int> res=countScans(a, x, v);
//     for(int x:res) cout<<x<<'\n';
// }

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