oj.uz

Submission #1088717

# Submission time Handle Problem Language Result Execution time Memory
1088717 2024-09-14T21:49:38 Z vladilius Curtains (NOI23_curtains) C++17
0 / 100
 1 ms 456 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
const int inf = 5e5 + 1;

struct ST{
    struct node{
        int mn, mn2;
    };
    vector<node> t;
    int n;
    ST(int ns){
        n = ns;
        t.assign(4 * n, {0, inf});
    }
    void merge(int& v){
        int vv = 2 * v;
        if (t[vv].mn < t[vv + 1].mn){
            t[v].mn = t[vv].mn;
            t[v].mn2 = min(t[vv + 1].mn, t[vv].mn2);
        }
        else {
            t[v].mn = t[vv + 1].mn;
            t[v].mn2 = min(t[vv].mn, t[vv + 1].mn2);
        }
    }
    void chmax(int v, int tl, int tr, int& l, int& r, int& x){
        if (l > tr || r < tl || t[v].mn >= x) return;
        if (l <= tl && tr <= r && t[v].mn2 > x){
            t[v].mn = x;
            return;
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        chmax(vv, tl, tm, l, r, x);
        chmax(vv + 1, tm + 1, tr, l, r, x);
        merge(v);
    }
    void chmax(int l, int r, int x){
        chmax(1, 1, n, l, r, x);
    }
    int get(int v, int tl, int tr, int& l, int& r){
        if (l > tr || r < tl) return inf;
        if (l <= tl && tr <= r) return t[v].mn;
        int tm = (tl + tr) / 2, vv = 2 * v;
        return min(get(vv, tl, tm, l, r), get(vv + 1, tm + 1, tr, l, r));
    }
    int get(int l, int r){
        return get(1, 1, n, l, r);
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, m, q; cin>>n>>m>>q;
    vector<int> st[n + 1];
    while (m--){
        int l, r; cin>>l>>r;
        st[r].pb(l);
    }
    vector<pii> qs[n + 1];
    for (int i = 1; i <= q; i++){
        int l, r; cin>>l>>r;
        qs[r].pb({l, i});
    }
    vector<int> out(q + 1);
    ST T(n);
    for (int r = 1; r <= n; r++){
        for (int l: st[r]){
            T.chmax(l, r, l);
        }
        for (auto [l, i]: qs[r]){
            out[i] = (T.get(l, r) >= l);
        }
    }
    
    for (int i = 1; i <= q; i++){
        cout<<(out[i] ? "YES" : "NO")<<"\n";
    }
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 456 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -