Submission #500726

#	Time	Username	Problem	Language	Result	Execution time	Memory
500726		pooty	Lightning Rod (NOI18_lightningrod)	C++17	100 / 100	1877 ms	262144 KiB

Main

#define REP(i, n) for(int i = 0; i < n; i ++)
#define REPL(i,m, n) for(int i = m; i < n; i ++)
#define FOREACH(it, l) for (auto it = l.begin(); it != l.end(); it++)
#define SORT(arr) sort(arr.begin(), arr.end())
#define LSOne(S) ((S)&-(S))
#define M_PI 3.1415926535897932384
#define INF 999999999
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef double ld;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int n;cin>>n;
	vii arr;
	int prev = -1;
	REP(i, n) {
		int x,y;cin>>x>>y;
		if (x== prev) {
			arr.back().second = max(arr.back().second, y);
		} else {
			arr.push_back({x,y});
		}
		prev = x;
	}
	int sze = arr.size();
	bool covered[sze];
	memset(covered, 0, sizeof(covered));
	int prevOffset = -1;
	REP(i, sze) {
		auto [x,y] = arr[i];
		int cur = x+y;
		if (cur <= prevOffset) {
			covered[i] = true;
		}
		prevOffset = max(cur, prevOffset);
	}
	prevOffset = -1;
	for (int i = sze-1; i >=0; i--) {
		auto [x,y] = arr[i];
		int dx = 1e9 - x;
		int cur = dx + y;
		if (cur <= prevOffset) {
			covered[i]= true;
		}
		prevOffset = max(cur, prevOffset);
	}
	int tot = sze;
	REP(i, sze) {
		if (covered[i]) tot--;
	}cout<<tot;
}

• 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