oj.uz

Submission #739818

# Submission time Handle Problem Language Result Execution time Memory
739818 2023-05-11T11:10:00 Z MODDI Lightning Rod (NOI18_lightningrod) C++14
66 / 100
 2000 ms 79256 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;
	for(int i = 0; i < n; i++){
		cin>>arr[i].first>>arr[i].second;
//		pq.push(mp(arr[i].second, i));
	}
	sort(arr.begin(), arr.end());
	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 2062 ms 79256 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 224 KB Output is correct
2 Correct 1 ms 212 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 212 KB Output is correct
6 Correct 1 ms 216 KB Output is correct
7 Correct 1 ms 308 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 224 KB Output is correct
2 Correct 1 ms 212 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 212 KB Output is correct
6 Correct 1 ms 216 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 308 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 224 KB Output is correct
2 Correct 1 ms 212 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 212 KB Output is correct
6 Correct 1 ms 216 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 308 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 3 ms 364 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 4 ms 316 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 224 KB Output is correct
2 Correct 1 ms 212 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 212 KB Output is correct
6 Correct 1 ms 216 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 308 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 3 ms 364 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 4 ms 316 KB Output is correct
14 Correct 219 ms 10168 KB Output is correct
15 Correct 241 ms 10324 KB Output is correct
16 Correct 300 ms 10144 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2051 ms 79064 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 2062 ms 79256 KB Time limit exceeded
2 Halted 0 ms 0 KB -