Untitled
unknown
plain_text
9 months ago
2.7 kB
2
Indexable
#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;
}Editor is loading...
Leave a Comment