Submission #739834

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
739834	2023-05-11T11:31:04 Z	MODDI	Lightning Rod (NOI18_lightningrod)	C++14	100 / 100	1916 ms	228084 KB

lightningrod

#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

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.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1460 ms	76196 KB	Output is correct
2	Correct	1472 ms	75960 KB	Output is correct
3	Correct	1423 ms	73928 KB	Output is correct

Subtask #2

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 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	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct

Subtask #4

21.0 / 21.0

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

Subtask #5

26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 ms	352 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	2 ms	340 KB	Output is correct
14	Correct	110 ms	7628 KB	Output is correct
15	Correct	109 ms	7740 KB	Output is correct
16	Correct	157 ms	7512 KB	Output is correct

Subtask #6

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1534 ms	78292 KB	Output is correct
2	Correct	1505 ms	78232 KB	Output is correct
3	Correct	1467 ms	76356 KB	Output is correct

Subtask #7

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1460 ms	76196 KB	Output is correct
2	Correct	1472 ms	75960 KB	Output is correct
3	Correct	1423 ms	73928 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	1 ms	352 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	2 ms	340 KB	Output is correct
17	Correct	110 ms	7628 KB	Output is correct
18	Correct	109 ms	7740 KB	Output is correct
19	Correct	157 ms	7512 KB	Output is correct
20	Correct	1534 ms	78292 KB	Output is correct
21	Correct	1505 ms	78232 KB	Output is correct
22	Correct	1467 ms	76356 KB	Output is correct
23	Correct	1755 ms	71240 KB	Output is correct
24	Correct	1916 ms	228084 KB	Output is correct
25	Correct	1818 ms	208660 KB	Output is correct