Submission #341091

#	Time	Username	Problem	Language	Result	Execution time	Memory
341091		ommivorous	Lightning Rod (NOI18_lightningrod)	C++14	19 / 100	2090 ms	245484 KiB

Main

/* Do what u love, love what u do */
// lightning rod 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define f first
#define s second
#define mp make_pair
#define For(i, l, r) for (int i = l; i < r; i++)
#define ForE(i, l, r) for (int i = l; i <= r; i++)
#define Ford(i, r, l) for (int i = r; i > l; i--)
#define FordE(i, r, l) for (int i = r; i >= l; i--)
#define Fora(i, a) for (auto i : a)
long double pi = 3.14159265359;
const ll inf = 1e18;
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	ll n , res = 0;
	cin >> n;
	bool used[n+1];
	memset(used,false,sizeof(used));
	ll dp[n+1];
	vector<pair<ll,ll>> point(n);
	For(i,0,n){
		cin >> point[i].f >> point[i].s;
	}
	ForE(i,1,n){
	   used[i] = true;
	}
	sort(point.begin(),point.end());
	ll x[n+1] , y[n+1];
	For(i,0,n){
		x[i+1] = point[i].f;
		y[i+1] = point[i].s;
	}
	dp[0] = -inf;
	ForE(i,1,n){
		dp[i] = max({dp[i-1],x[i]+y[i]});
	}
	ForE(i,1,n){
		if (x[i]+y[i]<=dp[i-1]){
			used[i] = false;
		}
	}
	dp[n+1] = -inf;
	FordE(i,n,1){
		dp[i] = max({dp[i+1],y[i]-x[i]});
	}
	ForE(i,1,n){
		if (y[i]-x[i]<=dp[i+1]){
			used[i] = false;
		}
	}
	ForE(i,1,n){
		if (used[i]){
			res++;
		}
	}
	cout << res << endl;
}

• Subtask 1: 0 / 4
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 0 / 21
• Subtask 5: 0 / 26
• Subtask 6: 0 / 10
• Subtask 7: 0 / 20