Submission #190381

#	Time	Username	Problem	Language	Result	Execution time	Memory
190381		mrtsima22	Lightning Rod (NOI18_lightningrod)	C++17	80 / 100	2024 ms	175496 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define two pair<int,int>
#define pb push_back
#define f first
#define s second
#define sz(container) (int)(container.size())
inline int bin(){
	int x=0;char ch=getchar();
	while (ch<'0'||ch>'9') ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return x;
}
int n;
stack<two>st;
int main(){
n=bin();
for(int i=1;i<=n;++i){
	int x=bin();
	int y=bin();
	bool ok=1;
	while(!st.empty()){
		int a=st.top().f;
		int b=st.top().s;
		if(x-a<=b-y){
			ok=0;
			break;
		}
		if(x-a<=y-b){
			st.pop();
		}else{
			break;
		}
	}
	if(ok){
		st.push({x,y});
	}
}
printf("%d\n",sz(st));

	// you should actually read the stuff at the bottom
}
/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?), slow multiset operations
	* do smth instead of nothing and stay organized
	* unordered_map, hash_map, scanf, calculate answer instead of ans*K
*/
/*


                   *         *
                  * *       * *
                 *   *     *   *
                *     *   *     *
                 *   *   * *   *
                  *   *   *   *
                   *   * *   *
                     *  *   *
					   *  *


*/

• 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: 0 / 20