Submission #1306651

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306651		vlomaczk	Rope (JOI17_rope)	C++20	15 / 100	2515 ms	135816 KiB

rope

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename TY>
struct MultiOrderedSet {
	ordered_set<pair<TY, int>> os;
	int cnt = 0;
	void insert(TY x) {
		os.insert({x, cnt++});
	}
	void erase(TY x) {
		int idx = os.order_of_key({x,-1});
		assert(idx < os.size());
		os.erase(*os.find_by_order(idx));
	}
	TY first() { return os.begin()->first; }
	TY last() { return os.rbegin()->first; }
	void clear() {
		while(os.size()) os.erase(*os.begin());
	}
	int size() { return os.size(); }
	bool empty() { return os.empty(); }
	int order_of_key(TY x) {
		return os.order_of_key({x, -1});
	}
	TY find_by_order(ll x) {
		return os.find_by_order(x)->first;
	}
};

struct DataStructure {
	MultiOrderedSet<int> os;
	vector<int> ile;
	int suma=0;

	DataStructure() : ile(1e6+1) {
		for(int i=0; i<=1e6; ++i) os.insert(0);
	}

	void dodaj(int x) {
		suma++;
		os.erase(ile[x]);
		ile[x]++;
		os.insert(ile[x]);
	}

	void usun(int x) {
		suma--;
		os.erase(ile[x]);
		ile[x]--;
		os.insert(ile[x]);
	}

	int cost() {
		return suma - os.last();
	}
};

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

	int n, m;
	cin >> n >> m;
	vector<int> a(n);
	for(int i=0; i<n; ++i) cin >> a[i];
	vector<pair<int, int>> pary1, pary2;
	vector<vector<int>> bucket1(m+1), bucket2(m+1);
	for(int i=0; i+1<n; i+=2) {
		pary1.push_back({a[i], a[i+1]});
		bucket1[a[i]].push_back(i/2);
		if(a[i]!=a[i+1]) bucket1[a[i+1]].push_back(i/2);
	}
	for(int i=1; i+1<n; i+=2) {
		pary2.push_back({a[i], a[i+1]});
		bucket2[a[i]].push_back(i/2);
		if(a[i]!=a[i+1]) bucket2[a[i+1]].push_back(i/2);
	}
	DataStructure d1, d2;
	for(int i=0; i<n; ++i) {
		d1.dodaj(a[i]);
		d2.dodaj(a[i]);
	}
	for(int c=1; c<=m; ++c) {
		ll res1 = 0;
		for(auto i : bucket1[c]) {
			d1.usun(a[i+i]);
			d1.usun(a[i+i+1]);
			if(a[i+i]!=c) res1++;
			if(a[i+i+1]!=c) res1++; 
		}
		if(c==a[n-1] && n%2) d1.usun(c);
		res1 += d1.cost();
		if(c==a[n-1] && n%2) d1.dodaj(c);
		for(auto i : bucket1[c]) {
			d1.dodaj(a[i+i]);
			d1.dodaj(a[i+i+1]);
		}
		
		ll res2 = 0;
		for(auto i : bucket2[c]) {
			d2.usun(a[i+i+1]);
			d2.usun(a[i+i+2]);
			if(a[i+i+1]!=c) res2++;
			if(a[i+i+2]!=c) res2++; 
		}
		if(c==a[n-1] && n%2==0) d2.usun(c);
		if(c==a[0]) d2.usun(c);
		res2 += d2.cost();
		if(c==a[0]) d2.dodaj(c);
		if(c==a[n-1] && n%2==0) d2.dodaj(c);
		for(auto i : bucket2[c]) {
			d2.dodaj(a[i+i+1]);
			d2.dodaj(a[i+i+2]);
		}
		cout << min(res1, res2) << "\n";
	}

	return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 0 / 30
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 20