제출 #270588

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

bubblesort2

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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl


#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//*find_by_order: iterator to kth elem (0-indexed)
//order_of_key: # of items < k (stictly less)


using ll = long long;

const ll mod = 1e9+7;
const int maxn = 1e6 + 5;
const ll inf = 1e18;

struct MaxLazySegmentTree {
    vector<ll> t, o;
    void init(int n) {
	n += 10;
	t.resize(4*n);
	o.resize(4*n);
    }
    
    void push(int v) {
	t[2*v]+=o[v];
	t[2*v+1]+=o[v];
	o[2*v]+=o[v];
	o[2*v+1]+=o[v];
	o[v]=0;
    }

    ll queryMax(int v, int tl, int tr, int l, int r) {
	if (l>tr||r<tl) return -inf;
	if (l<=tl&&tr<=r) {
	    return t[v];
	} else {
	    push(v);
	    int tm=(tl+tr)/2;
	    return max(queryMax(2*v,tl,tm,l,r),queryMax(2*v+1,tm+1,tr,l,r));
	}
    }

    void rangeAdd(int v, int tl, int tr, int l, int r, ll dx) {
	if (l>r) return;
	if (l>tr||r<tl) return;
	if (l<=tl&&tr<=r) {
	    t[v]+=dx;
	    o[v]+=dx;
	} else {
	    push(v);
	    int tm=(tl+tr)/2;
	    rangeAdd(2*v,tl,tm,l,r,dx);
	    rangeAdd(2*v+1,tm+1,tr,l,r,dx);
	    t[v]=max(t[2*v],t[2*v+1]);
	}
    }
};


template<typename T> struct bit1 {
    T add(T x, T y) {
	return x+y;
    }
    int n;
    vector<T> t;
    void init(int n) {
	this->n=n;
	t.resize(n+10);
    }
    T qry(int i) {
	assert(i>=1 && i<=n);
	T res=0;
	for (; i>0; i-=i&-i) res=add(res,t[i]);
	return res;
    }
    void upd(int i, T dx) {
	assert(i>=1 && i<=n);
	for (; i<=n; i+=i&-i) t[i]=add(t[i],dx);
    }
};



bool sorted(vector<int> a) {
    int n = a.size();
    for (int i=1; i<n; i++) {
	if (a[i] < a[i-1]) return false;
    }
    return true;
}

int brute(vector<int> a) {
    int n = a.size();
    int res = 0;
    while (!sorted(a)) {
	res++;
	for (int i=0; i<n-1; i++) {
	    if (a[i] > a[i+1]) swap(a[i], a[i+1]);
	}
    }
    return res;
}

int solve(vector<int> a) {
    vector<int> sa = a;
    int n = a.size();
    sort(sa.begin(), sa.end());
    map<int,vector<int>> inds;
    for (int i=n-1; i>=0; i--) {
	inds[sa[i]].push_back(i);
    }
    int mx = 0;

    for (int i=0; i<n; i++) {
	int to = inds[a[i]].back();
	if (to < i) {
	    mx = max(mx, i-to);
	}
	inds[a[i]].pop_back();
    }

    return mx;
}

int solveInversion(vector<int> a) {
    map<int,int> ind;
    ordered_set<pair<int,int>> os;
    int hi = 0;
    
    for (int x: a) {
	pair<int,int> cur = {x, ind[x]++};
	int lte = os.order_of_key(cur);
	int inv = int(os.size()) - lte;
	hi = max(hi, inv);
	os.insert(cur);
    }

    return hi;
}


void print(vector<int> a) {
    for (int i: a) cout<<i<<" ";
    cout<<endl;
}



vector<int> solveTask3(vector<int> A, vector<int> X, vector<int> V) {
    //cerr<<"task3"<<endl;
    
    int n = A.size();
    vector<set<int>> inds(102);
    for (int i=0; i<n; i++) {
	inds[A[i]].insert(i);
    }

    vector<int> ans;

    for (int q=0; q<(int)X.size(); q++) {
	int idx = X[q];
	int val = V[q];
	inds[A[idx]].erase(idx);
	A[idx] = val;
	inds[A[idx]].insert(idx);

	int mx = 0;
	int prev = 0;
	for (int i=1; i<=100; i++) {
	    if (inds[i].empty()) {
		continue;
	    }
	    int dest = prev + int(inds[i].size()) - 1;
	    int dist = *inds[i].rbegin() - dest;
	    mx = max(mx, dist);
	    prev += int(inds[i].size());
	}
	//assert(mx == brute(A));
	ans.push_back(mx);
    }

    return ans;
}



vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
    // if (max(*max_element(A.begin(),A.end()), *max_element(V.begin(),V.end())) <= 100) {
    // 	return solveTask3(A,X,V);
    // }
    int n = A.size();
    MaxLazySegmentTree tree; //queryMax, rangeAdd
    bit1<ll> bit;
    vector<int> ord;
    ord.push_back(-1);
    ord.push_back(0);
    for (auto x: A) ord.push_back(x);
    for (auto x: V) ord.push_back(x);
    ord.push_back(1000000001);
    sort(ord.begin(), ord.end());
    ord.erase(unique(ord.begin(), ord.end()), ord.end());
    int N = ord.size();
    tree.init(N);
    bit.init(N);

    map<int,set<int>> inds;
    for (int i=0; i<n; i++) {
	inds[A[i]].insert(i);
	int id = lower_bound(ord.begin(), ord.end(), A[i]) - ord.begin();
	bit.upd(id, +1);
    }
    for (auto p: inds) {
	int val = p.first;
	int rightmost = *p.second.rbegin();
	int id = lower_bound(ord.begin(), ord.end(), val) - ord.begin();
	tree.rangeAdd(1,1,N,id,id,+rightmost);
	int rnk = bit.qry(id-1) + int(p.second.size()) - 1;
	tree.rangeAdd(1,1,N,id,id,-rnk);
    }

    // watch(tree.queryMax(1,1,N,1,N));
    // watch(brute(A));
    // assert(tree.queryMax(1,1,N,1,N) == brute(A));
    // for (int j=1; j<=N; j++) {
    // 	if (inds[ord[j]].empty()) {
    // 	    assert(tree.queryMax(1,1,N,j,j)<=0);
    // 	}
    // }
    // for (int j=1; j<=N; j++) {
    // 	cout<<tree.queryMax(1,1,N,j,j)<<" ";
    // }
    // cout<<endl;


    auto clean = [&](int id) {
	ll val = tree.queryMax(1,1,N,id,id);
	tree.rangeAdd(1,1,N,id,id,-val);
    };


    // rightmost - rank
    // rank: | <me | + (| =me | - 1)


    // auto getRank = [&](int val) {
    // 	assert(inds[val].size());
    // 	int id = lower_bound(ord.begin(), ord.end(), val) - ord.begin();
    // 	return bit.qry(id-1) + int(inds[val].size()) - 1;
    // };

    int Q = X.size();
    vector<int> res(Q);
    for (int i=0; i<Q; i++) {
	int idx = X[i];
	// remove
	{
	    int id = lower_bound(ord.begin(), ord.end(), A[idx]) - ord.begin();
	    if ((int)inds[A[idx]].size() > 1) tree.rangeAdd(1,1,N,id,id,+1);
	    tree.rangeAdd(1,1,N,id+1,N,+1);
	    
	    if (idx == *inds[A[idx]].rbegin()) {
		tree.rangeAdd(1,1,N,id,id,-(*inds[A[idx]].rbegin()));
		inds[A[idx]].erase(idx);
		if (!inds[A[idx]].empty()) {
		    tree.rangeAdd(1,1,N,id,id,+(*inds[A[idx]].rbegin()));
		}
	    } else {
		inds[A[idx]].erase(idx);
	    }
	    
	    bit.upd(id,-1);
	    
	}


	// insert
	A[idx] = V[i];
	{
	    int id = lower_bound(ord.begin(), ord.end(), A[idx]) - ord.begin();
	    bit.upd(id,+1);
	    tree.rangeAdd(1,1,N,id+1,N,-1);
	    if (!inds[A[idx]].empty()) {
		tree.rangeAdd(1,1,N,id,id,-1);
		tree.rangeAdd(1,1,N,id,id,-(*inds[A[idx]].rbegin()));
	    }
	    inds[A[idx]].insert(idx);
	    tree.rangeAdd(1,1,N,id,id,+(*inds[A[idx]].rbegin()));


	    clean(id);
	    {
		int val = A[idx];
		int rightmost = *inds[val].rbegin();
		int id = lower_bound(ord.begin(), ord.end(), val) - ord.begin();
		tree.rangeAdd(1,1,N,id,id,+rightmost);
		int rnk = bit.qry(id-1) + int(inds[val].size()) - 1;
		tree.rangeAdd(1,1,N,id,id,-rnk);
	    }
	}

	// for (int j=1; j<=N; j++) {
	//     cout<<tree.queryMax(1,1,N,j,j)<<" ";
	// }
	// cout<<endl;
	
	res[i] = tree.queryMax(1,1,N,1,N);
	//cout<<res[i]<<": expect: "<<brute(A)<<endl;
	//assert(res[i] == brute(A));

	
	
    }

    return res;
}

// int main() {
//     ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

//     int n,q;
//     cin>>n>>q;
//     vector<int> a(n);
//     for (int i=0; i<n; i++) {
// 	cin>>a[i];
//     }
//     vector<int> x, v;
//     while (q--) {
// 	int i, val;
// 	cin>>i>>val;
// 	x.push_back(i);
// 	v.push_back(val);
//     }

//     auto res = countScans(a,x,v);
//     for (int i: res) cout<<i<<" ";
//     cout<<endl;
    
    
//     return 0;
// }

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