제출 #210368

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
210368		HNO2	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	2195 ms	80092 KiB

bubblesort2

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

std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V);

typedef long long ll;
const int maxn=5e5+7;
const int inf=INT_MAX;
const ll inff=1e18;
const ll mod=1e9+7;
#define pii pair<int,int>
#define mkp make_pair
#define F first
#define S second
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
//#define int ll

#ifdef HNO2
#define IOS
#else
#include <bubblesort2.h>
#define endl '\n'
#define IOS ios::sync_with_stdio(0); cin.tie(0);
#endif // HNO2

vector<ll> values;
ll a[maxn];
ll x[maxn],v[maxn];

const int C=1e8;

struct segtree
{
    int seg[maxn*2*4],tag[maxn*2*4];

    void init()
    {
        memset(seg,0,sizeof(seg));
        memset(tag,0,sizeof(tag));
    }

    void push(int now,int l,int r)
    {
        if (l==r||tag[now]==0)
        {
            tag[now]=0;
            return;
        }
        seg[now*2]+=tag[now];
        tag[now*2]+=tag[now];
        seg[now*2+1]+=tag[now];
        tag[now*2+1]+=tag[now];
        tag[now]=0;
    }

    void modify(int now,int l,int r,int ql,int qr,int vv)
    {
        if (l>=ql&&r<=qr)
        {
            seg[now]+=vv;
            tag[now]+=vv;
            return;
        }
        int m=(l+r)>>1;
        push(now,l,r);
        if (ql<=m) modify(now*2,l,m,ql,qr,vv);
        if (qr>m) modify(now*2+1,m+1,r,ql,qr,vv);
        seg[now]=max(seg[now*2],seg[now*2+1]);
    }

    int query()
    {
        return seg[1];
    }
}tree;

std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
	int n=sz(A),q=sz(X);
	vector<int> ans;
    for (int i=1;i<=n;i++) a[i]=A[i-1]*1ll*C+i,values.pb(A[i-1]*1ll*C+i);
    for (int i=1;i<=q;i++)
    {
        x[i]=X[i-1]+1;
        v[i]=V[i-1]*1ll*C+(X[i-1]+1);
        values.pb(V[i-1]*1ll*C+(X[i-1]+1));
    }
    //values.pb(-1);
    sort(all(values));
    values.resize(unique(all(values))-values.begin());

    for (int i=1;i<=n;i++) a[i]=lower_bound(all(values),a[i])-values.begin()+1;
    for (int i=1;i<=q;i++) v[i]=lower_bound(all(values),v[i])-values.begin()+1;

    int N=sz(values);
    tree.init();
    for (int i=1;i<=N;i++) tree.modify(1,1,N,i,i,-C+(values[i-1]%C));

    for (int i=1;i<=n;i++)
    {
        tree.modify(1,1,N,a[i],a[i],C);
        if (a[i]!=N) tree.modify(1,1,N,a[i]+1,N,-1);
    }

    for (int i=1;i<=q;i++)
    {
        if (a[x[i]]!=N) tree.modify(1,1,N,a[x[i]]+1,N,1);
        tree.modify(1,1,N,a[x[i]],a[x[i]],-C);
        a[x[i]]=v[i];
        if (a[x[i]]!=N) tree.modify(1,1,N,a[x[i]]+1,N,-1);
        tree.modify(1,1,N,a[x[i]],a[x[i]],C);
        ans.pb(tree.query()-1);
    }

	return ans;
}

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