Submission #739834

#	Time	Username	Problem	Language	Result	Execution time	Memory
739834		MODDI	Lightning Rod (NOI18_lightningrod)	C++14	100 / 100	1916 ms	228084 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 check(pii a, pii b){
	int c = b.first - a.first;
	if(a.second - b.second >= c)	return 1;
	if(b.second - a.second >= c)	return 2;
	return 0;
}
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));
	}
	bool jump = true;
	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;
	}
	else if(n <= 200000){
		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;
	}
	else{
		int ans = 0;
		stack<pii> st;
		for(int i = 0; i < n; i++){
			if(i == 0){
				st.push(arr[i]);
				continue;
			}
			while(!st.empty()){
				int x = check(st.top(), arr[i]);
				if(x == 0){
					st.push(arr[i]);
					break;
				}
				if(x==1)	break;
				st.pop();
				if(st.empty()) st.push(arr[i]);
			}
		}
		cout<<st.size()<<endl;
		return 0;
	}
}

Compilation message (stderr)

lightningrod.cpp: In function 'int main()':
lightningrod.cpp:150:7: warning: unused variable 'ans' [-Wunused-variable]
  150 |   int ans = 0;
      |       ^~~
lightningrod.cpp:100:7: warning: unused variable 'jump' [-Wunused-variable]
  100 |  bool jump = true;
      |       ^~~~

• 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: 20 / 20