Submission #104110

#	Time	Username	Problem	Language	Result	Execution time	Memory
104110		dupreez	Lightning Rod (NOI18_lightningrod)	C++14	66 / 100	2109 ms	263168 KiB

Main

#include <iostream>
#include <algorithm>
#include <cstring>
#include <sstream>
#include <map>
#include <queue>
#include <vector>
#define mk make_pair
#define pb push_back
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> pos;
const ll MOD = 1000000007,N=10000010;
int dp[N],n,ans,bt1[N],bt2[N];
pair<int, int> xy[N],yl[N];
priority_queue<pair<int, int> > q;

void ad(int v1, int v2,int bt[]) {
	while (v1 < N) {
		bt[v1] = max(bt[v1], v2);
		v1 += v1 & -v1;
	}
}

ll sm(int v1,int bt[]) {
	int v2 = -2147483647;
	while (v1 > 0) {
		v2 = max(v2, bt[v1]);
		v1 -= v1 & -v1;
	}
	return v2;
}


int main() {
	for (int i = 0; i < N; i++)bt1[i] = bt2[i] = (int)-2147483647;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) { 
		scanf("%d%d", &xy[i].first, &xy[i].second);
		yl[i] = mk(xy[i].second, i);
	}
	sort(yl + 1, yl + n + 1);
	for (int i = n; i >= 1; i--) {
		int ci = yl[i].second;
		int v1 = sm(ci,bt1),v2=-sm(n+1-ci,bt2);
		if (v1 >= xy[ci].first + xy[ci].second || v2 <= xy[ci].first - xy[ci].second)continue;
		ad(ci, xy[ci].first + xy[ci].second, bt1);
		ad(n + 1 - ci, -xy[ci].first + xy[ci].second,bt2);
		ans++;
	}
	cout << ans << endl;
	return 0;
}

Compilation message (stderr)

lightningrod.cpp: In function 'int main()':
lightningrod.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
lightningrod.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &xy[i].first, &xy[i].second);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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