Submission #709457

#	Time	Username	Problem	Language	Result	Execution time	Memory
709457		myrcella	Rope (JOI17_rope)	C++17	100 / 100	2362 ms	97368 KiB

rope

//by szh
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}

const int maxn = 1000010;

int n,m;
int c[maxn];
int cnt[maxn];
int ans[maxn];
int tmp[maxn],tmpp[maxn];

vector <int> v[maxn];

int tree[maxn*4];

void update(int c,int cl,int cr,int pos,int val) {
	if (cl==cr) tree[c]+=val;
	else {
		int mid=cl+cr>>1;
		if (pos<=mid) update(c<<1,cl,mid,pos,val);
		else update(c<<1|1,mid+1,cr,pos,val);
		tree[c] = max(tree[c<<1],tree[c<<1|1]);
	}
}

int query(int c,int cl,int cr,int l,int r) {
	if (l>r) return 0;
	if (l<=cl and cr<=r) return tree[c];
	int mid=cl+cr>>1;
	int ret = 0;
	if (l<=mid) ret = query(c<<1,cl,mid,l,r);
	if (r>mid) ret = max(ret,query(c<<1|1,mid+1,cr,l,r));
	return ret;
}

void solve(int id) {
	memset(tmp,0,sizeof(tmp));
	memset(tmpp,0,sizeof(tmpp));
	memset(tree,0,sizeof(tree));
	if (id==1) tmpp[c[0]]++;
	for (int i=id;i<n;i+=2) {
		if (i+1<n) tmpp[c[i]]+=2;
		else tmpp[c[i]]++;
		if (i+1<n and c[i]!=c[i+1]) {
			tmp[c[i]]++;
			tmp[c[i+1]]++;
			tmpp[c[i+1]]+=2;
			v[c[i]].pb(c[i+1]);
			v[c[i+1]].pb(c[i]);
		}
	}
	rep(i,1,m+1) update(1,1,m,i,cnt[i]);
	rep(i,1,m+1) {
		for (auto it:v[i]) update(1,1,m,it,-1);
		ans[i] = min(ans[i],n-cnt[i]);
		ans[i] = min(ans[i],(n-tmpp[i])-max(query(1,1,m,1,i-1),query(1,1,m,i+1,m))+tmp[i]);
	//	cout<<i<<" "<<query(1,1,m,i+1,m)<<endl;
		while (!v[i].empty()) update(1,1,m,v[i].back(),1),v[i].pop_back();
	}
}

int main() {
//	freopen("input.txt","r",stdin);	
	std::ios::sync_with_stdio(false);cin.tie(0);
	cin>>n>>m;
	rep(i,1,m+1) ans[i] = n;
	rep(i,0,n) {
		cin>>c[i];
		cnt[c[i]]++;
	}
	solve(0);
	solve(1);
	rep(i,0,m) cout<<ans[i+1]<<"\n";
	return 0;
}

Compilation message (stderr)

rope.cpp: In function 'void update(int, int, int, int, int)':
rope.cpp:39:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |   int mid=cl+cr>>1;
      |           ~~^~~
rope.cpp: In function 'int query(int, int, int, int, int)':
rope.cpp:49:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |  int mid=cl+cr>>1;
      |          ~~^~~

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