Submission #544234

#	Time	Username	Problem	Language	Result	Execution time	Memory
544234		Antekb	Rope (JOI17_rope)	C++14	100 / 100	534 ms	51616 KiB

rope

#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;
using ll = long long;
const int N=1e6+5;
int ile[N], ilez[N], ans[N], tab[N];
//map<pair<int, int>, int> edg;
int n, m;
void solve(int b){
	if(b==1)ilez[tab[0]]++;
	if((n&1)!=b)ilez[tab[n-1]]++;
	vector<pair<int, int> > V3;
	for(int i=0; i<n-1; i++){
		if((i&1)==b){
			int u=tab[i], v=tab[i+1];
			if(u>v)swap(u, v);
			ilez[u]++;
			ilez[v]++;
			if(u!=v){
				V3.push_back({u, v});
				//edg[{u, v}]++;
				//edg[{v, u}]++;
			}
		}
	}
	sort(V3.begin(), V3.end());
	vector<pair<pair<int, int>, int> > edg;
	for(auto i:V3){
		if(!edg.size() || i!=edg.back().st)edg.push_back({i, 0});
		edg.back().nd++;
	}
	vector<pair<int, int> > V;
	for(int i=1; i<=m; i++){
		V.push_back({ilez[i], i});
	}
	sort(V.begin(), V.end());
	for(int i=1; i<=m; i++){
		for(int j=V.size()-1; j>=0; j--){
			int a=V[j].nd, b=i;
			if(a>b)swap(a, b);
			int s=lower_bound(edg.begin(), edg.end(), make_pair(make_pair(a, b), 0))-edg.begin();
			if(a!=b && (s==edg.size() || edg[s].st!=make_pair(a, b))){
				ans[i]=max(ans[i], ilez[a]+ilez[b]);
				break;
			}
		}
	}
	for(auto i:edg){
		if(i.st.st<i.st.nd){
			int k=ilez[i.st.st]+ilez[i.st.nd]-i.nd;
			ans[i.st.st]=max(ans[i.st.st], k);
			ans[i.st.nd]=max(ans[i.st.nd], k);
		}
	}
	edg.clear();
	for(int i=1; i<=m; i++){
		ilez[i]=0;
	}
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	for(int i=0; i<n; i++)cin>>tab[i], ile[tab[i]]++;
	for(int i=1; i<=m; i++)ans[i]=ile[i];
	solve(0);
	solve(1);
	for(int i=1; i<=m; i++){
		cout<<n-ans[i]<<"\n";
	}
}

Compilation message (stderr)

rope.cpp: In function 'void solve(int)':
rope.cpp:43:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |    if(a!=b && (s==edg.size() || edg[s].st!=make_pair(a, b))){
      |                ~^~~~~~~~~~~~

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