oj.uz

Submission #739821

# Submission time Handle Problem Language Result Execution time Memory
739821 2023-05-11T11:14:41 Z MODDI Lightning Rod (NOI18_lightningrod) C++14
66 / 100
 2000 ms 79484 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
int n;
vector<pii> arr;
// abs(xi - xj) <= yi - yj -> we place on i
// let xi >= xj
// yj - xj <= yi - xi
// let xi < xj
// xj + yj <= yi + xi
int tree_levo[4 * 200100], tree_desno[4 * 200100];
// tree_levo - check left side
// tree_desno - check right side;
void build(int node, int l, int r){
	if(l == r){
		tree_levo[node] = -1e9;
		tree_desno[node] = -1e9;
	}
	else{
		int mid = (l + r) / 2;
		build(node*2, l, mid);
		build(node*2+1, mid+1, r);
		tree_levo[node] = max(tree_levo[node*2], tree_levo[node*2+1]);
		tree_desno[node] = max(tree_desno[node*2], tree_desno[node*2+1]);
	}
}
void update_levo(int node, int l, int r, int pos, int set){
	if(l == r)	tree_levo[node] = set;
	else{
		int mid = (l + r) / 2;
		if(pos <= mid)	update_levo(node*2, l, mid, pos, set);
		else update_levo(node*2+1, mid+1, r, pos, set);
		
		tree_levo[node] = max(tree_levo[node*2], tree_levo[node*2+1]);
	}
}
void update_desno(int node, int l, int r, int pos, int set){
	if(l == r)	tree_desno[node] = set;
	else{
		int mid = (l + r) / 2;
		if(pos <= mid)	update_desno(node*2, l, mid, pos, set);
		else update_desno(node*2+1, mid+1, r, pos, set);
		
		tree_desno[node] = max(tree_desno[node*2], tree_desno[node*2+1]);
	}
}
int query_levo(int node, int l, int r, int L, int R){
	if(r < L || l > R)	return -1e9;
	if(L <= l && r <= R)	return tree_levo[node];
	
	int mid = (l + r) / 2;
	int left = query_levo(node*2, l, mid, L, R);
	int right = query_levo(node*2+1, mid+1, r, L, R);
	return max(left, right);
}
int query_desno(int node, int l, int r, int L, int R){
	if(r < L || l > R)	return -1e9;
	if(L <= l && r <= R)	return tree_desno[node];
	int mid = (l + r) / 2;
	int left = query_desno(node*2, l, mid, L, R);
	int right = query_desno(node*2+1, mid+1, r, L, R);
	return max(left, right);
}
//1 1 -> 0
//3 2 -> 1
//4 3 -> 2
//5 1 -> 3
// 4 3
// update_desno na pozicija 2 -> -1
// update_levo na pozicija 2 -> 7
// 3 2
// query_desno za (0, 1) ke dade -1
// query_levo za (2, 3) ke dade 7
// 5 1
// 1 1
int main(){
	cin>>n;
	arr.resize(n);
	priority_queue<pii> pq;
	bool all = true;
	for(int i = 0; i < n; i++){
		cin>>arr[i].first>>arr[i].second;
		if(arr[i].second > 1)	all = false;
//		pq.push(mp(arr[i].second, i));
	}
	sort(arr.begin(), arr.end());
	if(all){
		int ans = 0;
		for(int i = 0; i < n; i++){
			if(arr[i].second==1)	ans++;
		}
		for(int i = 0; i < n; i++){
			if(arr[i].second == 0){
				if(i-1 >=0 && arr[i-1].second == 0 && i + 1 < n && arr[i+1].second == 0)	ans++;
				else if(i == 0 && arr[i+1].second == 0)	ans++;
				else if(i + 1== n && arr[i-1].second == 0)	ans++;
				else	continue;
			}
			else
				continue;
		}
		cout<<ans<<endl;
		return 0;
	}
	for(int i = 0; i < n; i++){
		pq.push(mp(arr[i].second, i));
	}
	build(1, 0, n-1);
	bool vis[n];
	memset(vis, false, sizeof vis);
	int ans = 0;
	while(!pq.empty()){
		pii here = pq.top();
		pq.pop();
		int pos = here.second;
//		cout<<pos<<endl;
//		cout<<query_levo(1, 0, n-1, 0, pos-1)<<" "<<arr[pos].second + arr[pos].first<<endl;
//		cout<<query_desno(1, 0, n-1, pos+1, n-1)<<" "<<arr[pos].second - arr[pos].first<<endl;
		if(query_levo(1, 0, n-1, 0, pos-1) >= arr[pos].second + arr[pos].first)	continue;
		else if(query_desno(1, 0, n-1, pos+1, n-1) >= arr[pos].second - arr[pos].first)	continue;
		else{
//			cout<<pos<<endl;
			ans++;
		}
		update_levo(1, 0, n-1, pos, arr[pos].second + arr[pos].first);
		update_desno(1, 0, n-1, pos, arr[pos].second - arr[pos].first);
	}
	cout<<ans<<endl;
	return 0;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2045 ms 76220 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 264 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 264 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 3 ms 340 KB Output is correct
12 Correct 3 ms 340 KB Output is correct
13 Correct 3 ms 340 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 264 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 3 ms 340 KB Output is correct
12 Correct 3 ms 340 KB Output is correct
13 Correct 3 ms 340 KB Output is correct
14 Correct 231 ms 8372 KB Output is correct
15 Correct 225 ms 8528 KB Output is correct
16 Correct 265 ms 8164 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2048 ms 79484 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2045 ms 76220 KB Time limit exceeded
2 Halted 0 ms 0 KB -