Untitled

 avatar
unknown
plain_text
12 days ago
2.7 kB
0
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;
}
Leave a Comment