oj.uz

Submission #965301

# Submission time Handle Problem Language Result Execution time Memory
965301 2024-04-18T09:58:08 Z pcc Cell Automaton (JOI23_cell) C++17
16 / 100
 179 ms 44484 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 = 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

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 1 ms 6488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 6488 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 65 ms 24776 KB Output is correct
2 Correct 63 ms 23500 KB Output is correct
3 Correct 56 ms 23864 KB Output is correct
4 Correct 65 ms 23348 KB Output is correct
5 Correct 57 ms 23368 KB Output is correct
6 Correct 56 ms 23236 KB Output is correct
7 Correct 67 ms 24132 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 2 ms 6760 KB Output is correct
11 Correct 61 ms 23244 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 24776 KB Output is correct
2 Correct 63 ms 23500 KB Output is correct
3 Correct 56 ms 23864 KB Output is correct
4 Correct 65 ms 23348 KB Output is correct
5 Correct 57 ms 23368 KB Output is correct
6 Correct 56 ms 23236 KB Output is correct
7 Correct 67 ms 24132 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 2 ms 6760 KB Output is correct
11 Correct 61 ms 23244 KB Output is correct
12 Correct 165 ms 41188 KB Output is correct
13 Correct 169 ms 43876 KB Output is correct
14 Correct 158 ms 44384 KB Output is correct
15 Correct 154 ms 44484 KB Output is correct
16 Correct 83 ms 30128 KB Output is correct
17 Correct 102 ms 30080 KB Output is correct
18 Correct 132 ms 32936 KB Output is correct
19 Correct 179 ms 44144 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 7004 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 7004 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

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