Submission #1206780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206780		emptypringlescan	Council (JOI23_council)	C++17	100 / 100	2643 ms	207028 KiB

council

#include <bits/stdc++.h>
using namespace std;
struct node{
	int s,e,m;
	node *l, *r;
	int val,lazy;
	node(int S, int E){
		s=S; e=E; m=(s+e)/2;
		val=-1e8; lazy=0;
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	void prop(){
		if(s!=e&&lazy){
			l->val+=lazy;
			l->lazy+=lazy;
			r->val+=lazy;
			r->lazy+=lazy;
			lazy=0;
		}
	}
	void update(int S, int E, int V){
		if(S<=s&&e<=E){
			lazy+=V;
			val+=V;
			return;
		}
		prop();
		if(E<=m) l->update(S,E,V);
		else if(S>m) r->update(S,E,V);
		else l->update(S,m,V),r->update(m+1,E,V);
		val=max(l->val,r->val);
	}
	int query(int S, int E){
		if(S<=s&&e<=E) return val;
		prop();
		if(E<=m) return l->query(S,E);
		else if(S>m) return r->query(S,E);
		else return max(l->query(S,m),r->query(m+1,E));
	}
} *root;
int getans(int x){
	int ret=0;
	if(x) ret=max(ret,root->query(0,x-1));
	if(x<(1<<21)-1) ret=max(ret,root->query(x+1,(1<<21)-1));
	return ret;
}
void upd(int bt, int v, int z){
	int cur=0;
	int l=1<<bt,mx=1<<21-1;
	while(cur<=mx){
		if(z) root->update(cur,min(mx,cur+l-1),v);
		else if(cur+l<=mx) root->update(cur+l,min(mx,cur+l+l-1),v);
		cur+=l+l;
	}
}
int occ[(1<<21)];
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,m;
	cin >> n >> m;
	pair<pair<int,int>,int> arr[n];
	int cnt[m];
	memset(cnt,0,sizeof(cnt));
	root=new node(0,(1<<21)-1);
	for(int i=0; i<n; i++){
		arr[i]={{0,i},0};
		for(int j=0; j<m; j++){
			int x;
			cin >> x;
			cnt[j]+=x;
			if(x) arr[i].second^=(1<<j);
			arr[i].first.first*=2;
			arr[i].first.first+=x;
		}
		occ[arr[i].second]++;
	}
	sort(arr,arr+n);
	for(int i=0; i<n; i++){
		if(i&&arr[i].first.first==arr[i-1].first.first) continue;
		root->update(arr[i].second,arr[i].second,1e8);
	}
	int cut=n/2;
	for(int i=0; i<n; i++){
		if(i&&arr[i].first.first==arr[i-1].first.first) continue;
		int cur=0;
		for(int j=0; j<m; j++){
			if(cnt[j]-((arr[0].second>>j)&1)-((arr[i].second>>j)&1) >= cut) cur++;
		}
		root->update(arr[i].second,arr[i].second,cur);
	}
	int ans[n];
	if(occ[arr[0].second]==1) ans[arr[0].first.second]=getans(arr[0].second);
	else ans[arr[0].first.second]=root->val;
	for(int i=1; i<n; i++){
		for(int j=0; j<m; j++){
			if(((arr[i-1].second>>j)&1)==((arr[i].second>>j)&1)) continue;
			if(cnt[j]==cut){
				if((arr[i].second>>j)&1){
					upd(j,-1,1);
				}
				else upd(j,1,1);
			}
			else if(cnt[j]==cut+1){
				if((arr[i].second>>j)&1){
					upd(j,-1,0);
				}
				else upd(j,1,0);
			}
		}
		if(occ[arr[i].second]==1) ans[arr[i].first.second]=getans(arr[i].second);
		else ans[arr[i].first.second]=root->val;
	}
	for(int i=0; i<n; i++) cout << ans[i] << '\n';
}

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 6 / 6
• Subtask 4: 19 / 19
• Subtask 5: 15 / 15
• Subtask 6: 22 / 22
• Subtask 7: 22 / 22