제출 #215928

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
215928		balbit	Bubble Sort 2 (JOI18_bubblesort2)	C++14	38 / 100	83 ms	95992 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define SZ(x) (int)(x.size())
#define ALL(x) x.begin(),x.end()
#define pb push_back
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<" "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
template<typename T> void _do(T && x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y){cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define bug(...)
#define IOS() ios::sync_with_stdio(0),cin.tie(0)
#define endl '\n'
#endif // BALBIT

const int maxn = 2e6+5;

multiset <int> pos[maxn];

int tag[maxn*4], s[maxn*4];

void push(int o, int l, int r){
    if (!tag[o]) return;
    s[o]+=tag[o];
    if (l!=r){
        tag[o*2+1]+=tag[o];
        tag[o*2+2]+=tag[o];
    }
    tag[o]=0;
}

int MX;

void MO(int L, int R, int v, int o=0, int l=0, int r=MX-1){
    push(o,l,r);
    if (l>R||r<L) return;
    if (l>=L&&r<=R) {
        tag[o]+=v; push(o,l,r); return;
    }
    int mid = (l+r)/2;
    MO(L,R,v, o*2+1,l,mid);
    MO(L,R,v, o*2+2,mid+1,r);
    s[o]=min(s[o*2+1],s[o*2+2]);
}

inline int big(multiset<int> & ms) {
    return SZ(ms)?-*(ms.rbegin()):0;
}

vector<signed> countScans(vector<signed> A,vector<signed> X,vector<signed> V){
	int Q=X.size();
	vector<signed> answer(Q);
	int n = SZ(A);
	vector<signed> tmp = A;
	for (int x : V) tmp.pb(x);
	SORT_UNIQUE(tmp);
	MX = SZ(tmp);

	for (int i = 0; i<n; ++i) {
        A[i] = lower_bound(ALL(tmp), A[i]) - tmp.begin();
        pos[A[i]].insert(i);
        MO(A[i]+1, MX-1,1);
	}
	for (int i = 0; i<Q; ++i) {
        V[i] = lower_bound(ALL(tmp), V[i]) - tmp.begin();
	}

    for (int i = 0; i<n; ++i) {
        if (big(pos[A[i]]) == -i) {
            MO(A[i],A[i],-i);
        }
    }
    bug(s[0]);
    for (int cnt = 0; cnt<Q; ++cnt) {
        int i = X[cnt];
        MO(A[i]+1, MX-1, -1);
        MO(A[i], A[i],-big(pos[A[i]]));
        bug(A[i], i);
        pos[A[i]].erase(pos[A[i]].find(i));
        MO(A[i],A[i], big(pos[A[i]]));

        A[i] = V[cnt];
        bug("insert",A[i],i);
        MO(A[i]+1, MX-1, 1);
        MO(A[i],A[i], -big(pos[A[i]]));
        pos[A[i]].insert(i);
        MO(A[i], A[i],big(pos[A[i]]));


        answer[cnt] = max(-s[0],0ll);

    }

	return answer;
}


#ifdef BALBIT
signed main(){
    IOS();
    vector<int> mo = (countScans({1,2,3,4},{0,2},{3,1}));
    for (int x : mo) bug(x);
}
#endif

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