Submission #190357

#	Time	Username	Problem	Language	Result	Execution time	Memory
190357		mrtsima22	Lightning Rod (NOI18_lightningrod)	C++17	80 / 100	2094 ms	113584 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,a,b,x,y;
bool ok;
two c;
stack<two>st;
int main(){
n=bin();
while(n--){
	x=bin();
	y=bin();
	ok=1;
	while(sz(st)){
		c=st.top();
		a=c.f;
		b=c.s;
		if(x-a<=b-y){
			ok=0;
			break;
		}
		if(x-a<=y-b){
			st.pop();
		}else{
			break;
		}
	}
	if(ok){
		st.push({x,y});
	}
}
cout<<sz(st)<<endl;

	// 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