Submission #1306656

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306656		vlomaczk	Rope (JOI17_rope)	C++20	100 / 100	542 ms	144288 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>;

struct DataStructure {
	vector<int> ile, cnt;
	int suma=0,max_val=0;

	DataStructure() : ile(1e6+1), cnt(1e6+1) {
		cnt[0] = 1e6;
	}

	void dodaj(int x) {
		suma++;
		cnt[ile[x]]--;
		ile[x]++;
		cnt[ile[x]]++;
		if(ile[x] > max_val) max_val = ile[x];
	}

	void usun(int x) {
		suma--;
		cnt[ile[x]]--;
		ile[x]--;
		cnt[ile[x]]++;
		while(cnt[max_val]==0) max_val--;
	}

	int cost() {
		return suma - max_val;
	}
};

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: 30 / 30
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 20 / 20