Submission #1207636

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207636		witek_cpp	Rope (JOI17_rope)	C++20	100 / 100	474 ms	89452 KiB

rope

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;

#define st first
#define nd second
#define f(a, c, b) for (int a = c; b > a; a++)
#define pb push_back
#define all(a) a.begin(), a.end()
#define wczytaj(a, c, n) a.resize(n); f(i, c, n) cin >> a[i];
#define sz(a) int(a.size())
#define wypisz(a, c) f(i, c, sz(a)) cout << a[i] << " "; cout << "\n";

int n, m;

vector<int> a;
vector<int> wstp;

vector<int> ile_aktl_dodaje_p;
vector<int> ile_aktl_dodaje_np;

vector<int> ile_jest_takich_p;
vector<int> ile_jest_takich_np;
vector<vector<int>> ind;
vector<int> odp;

pair<int, int> maksy;

int aktl_maks_p;
int aktl_maks_np;

void odejmij_p(int kolor) {
	//cout << "odjemujemy p kolor " << kolor << "\n";
	ile_aktl_dodaje_p[kolor]--;
	ile_jest_takich_p[ile_aktl_dodaje_p[kolor]]++;
	ile_jest_takich_p[ile_aktl_dodaje_p[kolor] + 1]--;
	//cout << "kolor " << kolor << " dodaje teraz " << ile_aktl_dodaje_p[kolor] << " dla p ile jest takich ktore dodaja do p " << aktl_maks_p << " " << ile_jest_takich_p[aktl_maks_p] << "\n";
	if (ile_jest_takich_p[aktl_maks_p] == 0) aktl_maks_p--;
}

void odejmij_np(int kolor) {
	//cout << "odejmujemy np kolor " << kolor << "\n";
	ile_aktl_dodaje_np[kolor]--;
	ile_jest_takich_np[ile_aktl_dodaje_np[kolor]]++;
	ile_jest_takich_np[ile_aktl_dodaje_np[kolor] + 1]--;
	if (ile_jest_takich_np[aktl_maks_np] == 0) aktl_maks_np--;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	
	wczytaj(a, 0, n);
	wstp.resize(m + 1, 0);
	ind.resize(m + 1);
	f(i, 0, n) {wstp[a[i]]++; ind[a[i]].pb(i);}
	
	if (m == 0) {
		cout << 0;
		return 0;
	}
	
	ile_aktl_dodaje_np.resize(m + 1, 0);
	ile_aktl_dodaje_p.resize(m + 1, 0);
	ile_jest_takich_p.resize(n + 1, 0);
	ile_jest_takich_np.resize(n + 1, 0);
	
	f(i, 1, m + 1) {
		ile_aktl_dodaje_np[i] = wstp[i];
		ile_aktl_dodaje_p[i] = wstp[i];
		ile_jest_takich_np[wstp[i]]++;
		ile_jest_takich_p[wstp[i]]++;
	}
		
	maksy = {1, -1};
	f(i, 2, m + 1) {
		if (wstp[maksy.st] <= wstp[i]) {maksy.nd = maksy.st; maksy.st = i;}
		else if (wstp[i] >= wstp[maksy.nd]) maksy.nd = i; 
	}
	
	//cout << "maksy na start " << maksy.st << " " << maksy.nd << "\n";
	
	odp.resize(m + 1, 0);
		
	f(i, 1, m + 1) {
		//cout << "rozwazamy kolor " << i << "\n";
		ile_aktl_dodaje_np[i] = 0;
		ile_aktl_dodaje_p[i] = 0;
		
		ile_jest_takich_np[wstp[i]]--;
		ile_jest_takich_np[0]++;
		ile_jest_takich_p[wstp[i]]--;
		ile_jest_takich_p[0]++;
		
		/*f(i, 1, m + 1) {
			cout << "ind " << i << "   ile aktl dodaje p " << ile_aktl_dodaje_p[i] << "     a np dodaje " << ile_aktl_dodaje_np[i] << "\n";
		}*/
		
		if (i == maksy.st) aktl_maks_np = aktl_maks_p = wstp[maksy.nd];
		else aktl_maks_np = aktl_maks_p = wstp[maksy.st];
		
		//cout << "aktl maks p " << aktl_maks_p << "    aktl maks np " << aktl_maks_np << "\n";
		
		for (int ele: ind[i]) {
			if (ele%2 == 0) {
				if (ele != (n - 1) && a[ele + 1] != i) {
					odejmij_p(a[ele + 1]);
				}
				if (ele != 0 && a[ele - 1] != i) {
					odejmij_np(a[ele - 1]);
				}
			} else {
				if (a[ele - 1] != i) {
					odejmij_p(a[ele - 1]);
				}
				if (ele != (n - 1) && a[ele + 1] != i) {
					odejmij_np(a[ele + 1]);
				}
			}
		}
		//cout << "aktl maks p " << aktl_maks_p << "    aktl maks np " << aktl_maks_np << "\n";
		odp[i] = (n - wstp[i]) - max(aktl_maks_np, aktl_maks_p);
		ile_aktl_dodaje_np[i] = wstp[i];
		ile_aktl_dodaje_p[i] = wstp[i];
		ile_jest_takich_np[wstp[i]]++;
		ile_jest_takich_p[wstp[i]]++;
		ile_jest_takich_np[0]--;
		ile_jest_takich_p[0]--;
		for (int ele: ind[i]) {
			if (ele != 0 && a[ele - 1] != i) {
				ile_jest_takich_np[ile_aktl_dodaje_np[a[ele - 1]]]--;
				ile_jest_takich_np[wstp[a[ele - 1]]]++;
				ile_aktl_dodaje_np[a[ele - 1]] = wstp[a[ele - 1]];
				ile_jest_takich_p[ile_aktl_dodaje_p[a[ele - 1]]]--;
				ile_jest_takich_p[wstp[a[ele - 1]]]++;
				ile_aktl_dodaje_p[a[ele - 1]] = wstp[a[ele - 1]];
			} 
			if (ele != n - 1 && a[ele + 1] != i) {
				ile_jest_takich_np[ile_aktl_dodaje_np[a[ele + 1]]]--;
				ile_jest_takich_np[wstp[a[ele + 1]]]++;
				ile_aktl_dodaje_np[a[ele + 1]] = wstp[a[ele + 1]];
				ile_jest_takich_p[ile_aktl_dodaje_p[a[ele + 1]]]--;
				ile_jest_takich_p[wstp[a[ele + 1]]]++;
				ile_aktl_dodaje_p[a[ele + 1]] = wstp[a[ele + 1]];
			}
		}
	}
	
	f(i, 1, m + 1) cout << odp[i] << "\n";
	return 0;
}

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