Submission #887039

#	Time	Username	Problem	Language	Result	Execution time	Memory
887039		underwaterkillerwhale	Curtains (NOI23_curtains)	C++14	100 / 100	767 ms	83236 KiB

curtains

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
#define iter(id, v) for (auto id : v)
#define ii pair<ll,ll>
#define fs first
#define se second
#define pb push_back
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()
#define bit(msk, i) ((msk >> i) & 1)

template<typename A, typename B> ostream& operator<<(ostream& out, const pair<A, B> &v) {
    out << "(" << v.fs << "," << v.se << ") ";
    return out;
}

//#ifndef ONLINE_JUDGE
//#include "debug.h"
//#else
//#define deb(...) 23
//#define ____
//#endif

mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) {
    return uniform_int_distribution<ll> (l, r)(rd);
}

const ll N = 5e5 + 7;
const ll Mod = 1e9 + 7;
const ll szBL = 650;
const ll INF = 2e9;
const ll B = 137;

ll n, m, Q;
vector<int> events[N];
vector<pair<int,int>> query[N];

struct Segment_Tree {
    ll Range;
    ll st[N << 2], lz[N << 2];

    void init(ll n) {
        Range = n;
    }

    void down (ll id) {
        rep (i, id << 1, id << 1 | 1) {
            lz[i] = max(lz[id], lz[i]);
            st[i] = max(lz[id], st[i]);
        }
        lz[id] = 0;
    }

    void update (ll id, ll l, ll r, ll u, ll v, ll val) {
        if (l > v or r < u)
            return;
        if (l >= u && r <= v) {
            st[id] = max(st[id], val);
            lz[id] = max(lz[id], val);
            return;
        }
        down(id);
        ll mid = l + r >> 1;
        update (id << 1, l, mid, u, v, val);
        update (id << 1 | 1, mid + 1, r, u, v, val);
        st[id] = min(st[id << 1], st[id << 1 | 1]);
    }

    ll get (ll id, ll l, ll r, ll u, ll v) {
        if (l > v or r < u) return INF;
        if (l >= u && r <= v) return st[id];
        down(id);
        ll mid = l + r >> 1;
        return min(get (id << 1, l, mid, u, v), get (id << 1 | 1, mid + 1, r, u, v));
    }

    void update (ll u, ll v, ll val) {
        update (1, 1, Range, u, v, val);
    }
    ll get (ll u, ll v) {
        return get (1, 1, Range, u, v);
    }
}ST;

void chloe_solution() {
    cin >> n >> m >> Q;
    ST.init(n);
    rep (i, 1, m) {
        ll L, R;
        cin >> L >> R;
        events[R].pb(L);
    }
    rep (i, 1, Q) {
        ll S, E;
        cin >> S >> E;
        query[E].pb({S, i});
    }
    vector<int> Ans(Q + 2);
    rep (i, 1, n) {
        ll R = i;
        iter (&L, events[R]) {
            ST.update(L, R, L);
        }
        iter (&id, query[R]) {
            ll L = id.fs;
            ll idx = id.se;
            if (ST.get(L, R) == L) {
                Ans[idx] = 1;
            }
        }
    }
    rep (i, 1, Q) if (Ans[i]) cout <<"YES\n"; else cout <<"NO\n";
}

#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);

int main() {
//    file("c");
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll num_Test = 1;
//    cin >> num_Test;
    while(num_Test--)
        chloe_solution();
}
/*
7 1
1 3 4 5 4 4 1
2 3 6


*/

Compilation message (stderr)

curtains.cpp: In member function 'void Segment_Tree::update(long long int, long long int, long long int, long long int, long long int, long long int)':
curtains.cpp:69:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |         ll mid = l + r >> 1;
      |                  ~~^~~
curtains.cpp: In member function 'long long int Segment_Tree::get(long long int, long long int, long long int, long long int, long long int)':
curtains.cpp:79:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   79 |         ll mid = l + r >> 1;
      |                  ~~^~~

• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 36 / 36
• Subtask 6: 20 / 20