Submission #341090

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
341090	2020-12-29T01:42:11 Z	ommivorous	Lightning Rod (NOI18_lightningrod)	C++14	7 / 100	2000 ms	262144 KB

lightningrod

/* 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,true,sizeof(used));
	used[0] = used[n+1] = false;
	ll dp[n+1];
	vector<pair<ll,ll>> point(n);
	For(i,0,n){
		cin >> point[i].f >> point[i].s;
	}
	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-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+1]){
			used[i] = false;
		}
	}
	ForE(i,1,n){
		if (used[i]){
			res++;
		}
	}
	cout << res << endl;
}

Subtask #1

0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2088 ms	262144 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	388 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct

Subtask #3

0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	388 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Incorrect	1 ms	364 KB	Output isn't correct
10	Halted	0 ms	0 KB	-

Subtask #4

0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	388 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Incorrect	1 ms	364 KB	Output isn't correct
10	Halted	0 ms	0 KB	-

Subtask #5

0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	388 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Incorrect	1 ms	364 KB	Output isn't correct
10	Halted	0 ms	0 KB	-

Subtask #6

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2078 ms	262144 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	2088 ms	262144 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-