제출 #1333654

#제출 시각아이디문제언어결과실행 시간메모리
1333654viettrungCurtains (NOI23_curtains)C++20
100 / 100
565 ms30828 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define f(i, a, b) for(int i = a; i <= b; i++)
#define fi first
#define se second
#define mll map<ll, ll>
#define sll set<ll>
const ll du = 1e9 + 7;
const ll ars = 5e5 + 5;

int n, m, q;

struct Dt{
    int t, l, r, id;
    bool operator<(const Dt & x)const{
        return r < x.r || (r == x.r && t < x.t);
    }
};

struct Dt2{
    int mx, lef, rig;
}st[4 * ars];



void build(int id, int l, int r){
    st[id] = {-1, -1, -1};
    if(l == r){
        st[id].mx = l - 1;
        return;
    }
    int mid = (l + r) / 2;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);
}

void merge_lz(int id, int ul, int ur){
    //cout << st[id].lef << " " << st[id].rig << " " << ul << " " << ur << '\n';
    if(st[id].lef == -1 || ul <= st[id].lef){
        st[id].lef = ul;
        st[id].rig = ur;
    }
    else if(ul <= st[id].rig){
        st[id].rig = ur;
    }
}

void push(int id){
    if(st[id].lef == -1) return;

    merge_lz(id * 2, st[id].lef, st[id].rig);
    merge_lz(id * 2 + 1, st[id].lef, st[id].rig);

    st[id].lef = st[id].rig = -1;
}

void update(int id, int l, int r, int u, int v, int ul, int ur){
    if(l > v || r < u) return;

    if(u <= l && r <= v){
        merge_lz(id, ul, ur);
        return;
    }

    push(id);

    int mid = (l + r) / 2;
    update(id * 2, l, mid, u, v, ul, ur);
    update(id * 2 + 1, mid + 1, r, u, v, ul, ur);
}

int get(int id, int l, int r, int p){
    if(l == r){
        if(st[id].lef != -1){
            if(st[id].mx >= st[id].lef){
                st[id].mx = max(st[id].mx, st[id].rig);
            }
            st[id].lef = st[id].rig = -1;
        }
        return st[id].mx;
    }

    push(id);

    int a;
    int mid = (l + r) / 2;
    if (p <= mid) a = get(id * 2, l, mid, p);
    else a = get(id * 2 + 1, mid + 1, r, p);
    return a;
}

bool ans[ars];

void sub6(){
    vector<Dt> v;
    for(int i = 1; i <= m; i++){
        int l, r;
        cin >> l >> r;
        v.pb({0, l, r, i});
    }
    for(int i = 1; i <= q; i++){
        int s, e;
        cin >> s >> e;
        v.pb({1, s, e, i});
    }
    sort(v.begin(), v.end());

    build(1, 1, n);

    for(auto[t, l, r, id] : v){
        //cout << t << " " << l << " " << r << " " << id << '\n';
        if(t == 0)
            update(1, 1, n, 1, l, l - 1, r);
        else{
            auto cur = get(1, 1, n, l);
            //cout << cur << '\n';
            if(cur >= r)
                ans[id] = true;
        }
    }
    for(int i = 1; i <= q; i++)
        cout << (ans[i] ? "YES" : "NO") << '\n';

}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define task "tenshi"
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    cin >> n >> m >> q;
    //if(n <= 2000) sub3();
    sub6();
}

컴파일 시 표준 에러 (stderr) 메시지

curtains.cpp: In function 'int main()':
curtains.cpp:133:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
curtains.cpp:134:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...