Submission #739825

#	Time	Username	Problem	Language	Result	Execution time	Memory
739825		MODDI	Lightning Rod (NOI18_lightningrod)	C++14	80 / 100	2017 ms	206348 KiB

Main

#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(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	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);
		}
//		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: 4 / 4
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 21 / 21
• Subtask 5: 26 / 26
• Subtask 6: 10 / 10
• Subtask 7: 0 / 20