Untitled
#include <bits/stdc++.h> using namespace std; #define Chris "test" #define FOR(i, a, b) for(int i = (a); i < (b); ++i) #define FORD(i, a, b) for(int i = (a); i <= (b); ++i) #define REP(i, a, b) for(int i = (a); i > (b); --i) #define REPD(i, a, b) for(int i = (a); i >= (b); --i) #define FORE(i, v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); i++) #define All(v) (v).begin(), (v).end() #define MARK(i) (1LL << (i)) #define BIT(x, i) (((x) >> (i)) & 1) #define pb push_back #define pf push_front #define pob pop_back #define pof pop_front #define fi first #define se second #define el "\n" #define Chris_No_Luv signed main() #define faster ios_base::sync_with_stdio(false); cin.tie(nullptr); #define file(Chris) if(fopen(Chris".inp", "r")){freopen(Chris".inp", "r", stdin);freopen(Chris".out", "w", stdout);} #define BIT(x, i) (((x) >> (i)) & 1) typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<int, int> pii; typedef vector<int> vii; typedef set<int> sii; typedef map<int, int> mii; typedef stack<int> sti; typedef deque<int> dqi; typedef queue<int> quei; const int mod = (int) 1e5; const int INF = (int) 1e9; int n; vector<pair<ll, ll>> a; vii b, c; void tinh1() { deque<pair<ll, ll>> de; de.pb({0, 1}); ll t = 0; FORD(i, 2, n * 2) { pair<ll, ll> x; x.fi = de.back().fi + a[i - 1].fi - a[i - 1].se; x.se = i; while(!de.empty() && x.fi <= de.back().fi) de.pob(); de.pb(x); if(i > n) { t += a[i - n - 1].fi - a[i - n - 1].se; if(!de.empty() && de.front().se < i - n) de.pof(); b[i - n] = de.front().fi - t >= 0 ? 1 : 0; } } } void tinh2() { deque<pair<ll, ll>> de; de.pb({0, n + n}); ll t = 0; REPD(i, n * 2 - 1, 1) { pair<ll, ll> x; x.fi = de.back().fi + a[i + 1].fi - a[i].se; x.se = i; while(!de.empty() && x.fi <= de.back().fi) de.pob(); de.pb(x); if(i <= n) { if(i != n) t += a[i + n].se - a[i + n + 1].fi; if(!de.empty() && de.front().se > i + n) de.pof(); c[i] = de.front().fi + t >= 0 ? 1 : 0; } } } Chris_No_Luv { faster cin >> n; a.resize(n + n + 1); b.resize(n + 1); c.resize(n + 1); FORD(i, 1, n) { cin >> a[i].fi >> a[i].se; a[i + n] = a[i]; } tinh1(); tinh2(); FORD(i, 1, n) { if(!b[i] && !c[i]) cout << "NO\n"; else cout << "YES\n"; } return 0; }
Leave a Comment