Submission #965301

#	Time	Username	Problem	Language	Result	Execution time	Memory
965301		pcc	Cell Automaton (JOI23_cell)	C++17	16 / 100	179 ms	44484 KiB

cell

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

#define pii pair<int,int>
#define fs first
#define sc second
#define ll long long

const int mxn = 5e5+10;
int N,Q;

struct D{
	ll t,tp,a,b;
	D(){}
	D(ll tt,ll ttp,ll aa,ll bb = 0):a(aa),b(bb),t(tt),tp(ttp){}
	bool operator<(D b)const{
		return t==b.t?tp<b.tp:t<b.t;
	}
};


struct DSU{
	int dsu[mxn],sz[mxn];
	int cc;
	DSU(){}
	void init(int n){
		for(int i = 0;i<=n;i++){
			dsu[i] = i,sz[i] = 1;
			cc++;
		}
		cc = n;
		return;
	}
	int root(int k){
		return k == dsu[k]?k:dsu[k] = root(dsu[k]);
	}
	void onion(int a,int b){
		a = root(a),b = root(b);
		if(a == b)return;
		if(sz[a]<sz[b])swap(a,b);
		cc--;
		dsu[b] = a;
		sz[a] += sz[b];
		return;
	}
};

DSU dsu;
vector<D> all;
int arr[mxn];
ll ans[mxn];
ll sum = 0;

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>Q;
	for(int i = 0;i<N;i++){
		cin>>arr[i]>>arr[i];
	}
	sort(arr,arr+N);
	dsu.init(N);
	for(int i = 1;i<N;i++){
		if((arr[i]-arr[i-1])&1){
			all.push_back(D(arr[i]-arr[i-1],1,(arr[i]-arr[i-1])+1));
			all.push_back(D(arr[i]-arr[i-1],2,i-1,i));
			all.push_back(D(arr[i]-arr[i-1]+1,1,(arr[i]-arr[i-1])-1));
		}
		else{
			all.push_back(D(arr[i]-arr[i-1],1,arr[i]-arr[i-1]+1));
			all.push_back(D(arr[i]-arr[i-1],2,i-1,i));
			all.push_back(D(arr[i]-arr[i-1]+1,1,arr[i]-arr[i-1]-1));
		}
	}
	for(int i = 0;i<Q;i++){
		ll k;
		cin>>k;
		all.push_back(D(k,3,i));
	}
	sort(all.begin(),all.end());
	ll nowt = 0;
	for(auto &i:all){
		sum += (i.t-nowt)*4*dsu.cc;
		nowt = i.t;
		if(i.tp == 3){
			if(!i.t)ans[i.a] = N;
			else ans[i.a] = sum;
		}
		else if(i.tp == 1)sum -= i.a;
		else dsu.onion(i.a,i.b);
	}
	for(int i = 0;i<Q;i++)cout<<ans[i]<<'\n';
	return 0;
}

Compilation message (stderr)

cell.cpp: In constructor 'D::D(long long int, long long int, long long int, long long int)':
cell.cpp:13:12: warning: 'D::b' will be initialized after [-Wreorder]
   13 |  ll t,tp,a,b;
      |            ^
cell.cpp:13:5: warning:   'long long int D::t' [-Wreorder]
   13 |  ll t,tp,a,b;
      |     ^
cell.cpp:15:2: warning:   when initialized here [-Wreorder]
   15 |  D(ll tt,ll ttp,ll aa,ll bb = 0):a(aa),b(bb),t(tt),tp(ttp){}
      |  ^

• Subtask 1: 0 / 4
• Subtask 2: 0 / 12
• Subtask 3: 8 / 8
• Subtask 4: 8 / 8
• Subtask 5: 0 / 17
• Subtask 6: 0 / 25
• Subtask 7: 0 / 26