Submission #886806

#	Time	Username	Problem	Language	Result	Execution time	Memory
886806		thangdz2k7	Curtains (NOI23_curtains)	C++17	100 / 100	767 ms	78516 KiB

curtains

#include <bits/stdc++.h>
#define F first
#define S second
#define ii pair <int, int>
#define pb push_back

using namespace std;

const int N = 5e5 + 5;

int n, m, q;
int s[N], e[N], ans[N];
vector <int> event[N], query[N];

int Min[4 * N], lazy[4 * N];

void down(int s){
    for (int i = 2 * s; i <= 2 * s + 1; ++ i){
        lazy[i] = max(lazy[i], lazy[s]);
        Min[i] = max(Min[i], lazy[s]);
    }
    lazy[s] = 0;
}

void update(int s, int l, int r, int u, int v, int val){
    if (u <= l && r <= v) {
        Min[s] = max(Min[s], val), lazy[s] = max(lazy[s], val);
        return;
    }
    int mid = l + r >> 1;
    down(s);
    if (mid >= u) update(2 * s, l, mid, u, v, val);
    if (mid + 1 <= v) update(2 * s + 1, mid + 1, r, u, v, val);
    Min[s] = min(Min[2 * s], Min[2 * s + 1]);
}

int get(int s, int l, int r, int u, int v){
    if (r < u or l > v) return 1e9;
    if (u <= l && r <= v) return Min[s];
    down(s);
    int mid = l + r >> 1;
    return min(get(2 * s, l, mid, u, v), get(2 * s + 1, mid + 1, r, u, v));
}

void solve(){
    cin >> n >> m >> q;
    for (int i = 1; i <= m; ++ i){
        int l, r;
        cin >> l >> r;
        event[r].pb(l);
    }

    for (int i = 1; i <= q; ++ i){
        cin >> s[i] >> e[i];
        query[e[i]].pb(i);
    }

    for (int i = 1; i <= n; ++ i){
        for (int l : event[i]) update(1, 1, n, l, i, l);
        for (int k : query[i]){
            if (get(1, 1, n, s[k], i) >= s[k]) ans[k] = 1;
        }
    }

    for (int i = 1; i <= q; ++ i) if (ans[i]) cout << "YES" << '\n';
    else cout << "NO" << '\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

Compilation message (stderr)

curtains.cpp: In function 'void update(int, int, int, int, int, int)':
curtains.cpp:30:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |     int mid = l + r >> 1;
      |               ~~^~~
curtains.cpp: In function 'int get(int, int, int, int, int)':
curtains.cpp:41:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |     int 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