Submission #341186

#	Time	Username	Problem	Language	Result	Execution time	Memory
341186		ommivorous	Lightning Rod (NOI18_lightningrod)	C++14	100 / 100	719 ms	161248 KiB

Main

/* Do what u love, love what u do */
#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;
stack<pair<ll,ll>> st;
ll readint () {
	bool minus = false;
	ll result = 0;
	char ch;
	ch = getchar();
	while (true) {
		if (ch == '-') break;
		if (ch >= '0' && ch <= '9') break;
		ch = getchar();
	}
	if (ch == '-') minus = true; else result = ch-'0';
	while (true) {
		ch = getchar();
		if (ch < '0' || ch > '9') break;
		result = result*10 + (ch - '0');
	}
	if (minus)
		return -result;
	else
		return result;
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n = readint();
    ForE(i,1,n){
        bool ok = true;
        ll x = readint();
        ll y = readint();
        while(!st.empty()){
            auto t = st.top();
            if (x+y<=t.f+t.s){
                ok = false;
                break;
            }
            if (x-y<=t.f-t.s){
                st.pop();
            }
            else {
                break;
            }
        }
        if (ok){
            st.push(mp(x,y));
        }
    }
    cout << st.size();
}

• 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