oj.uz

Submission #965299

# Submission time Handle Problem Language Result Execution time Memory
965299 2024-04-18T09:56:20 Z pcc Cell Automaton (JOI23_cell) C++17
8 / 100
 157 ms 62452 KB 
#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 = 1e5+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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 20928 KB Output is correct
2 Correct 70 ms 20160 KB Output is correct
3 Correct 57 ms 20312 KB Output is correct
4 Correct 60 ms 21016 KB Output is correct
5 Correct 60 ms 21136 KB Output is correct
6 Correct 57 ms 20416 KB Output is correct
7 Correct 59 ms 20416 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 740 KB Output is correct
11 Correct 58 ms 21304 KB Output is correct

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 20928 KB Output is correct
2 Correct 70 ms 20160 KB Output is correct
3 Correct 57 ms 20312 KB Output is correct
4 Correct 60 ms 21016 KB Output is correct
5 Correct 60 ms 21136 KB Output is correct
6 Correct 57 ms 20416 KB Output is correct
7 Correct 59 ms 20416 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 740 KB Output is correct
11 Correct 58 ms 21304 KB Output is correct
12 Runtime error 157 ms 62452 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -