Submission #1333509

#TimeUsernameProblemLanguageResultExecution timeMemory
1333509viettrungCurtains (NOI23_curtains)C++20
20 / 100
376 ms30572 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;
pair<int, int> a[ars];
int f[ars];

vector<int> pos[ars];
bool bp[2005][2005];
void sub3(){
    for(int i = 1; i <= m; i++){
        cin >> a[i].fi >> a[i].se;
        pos[a[i].se].pb(a[i].fi);
    }
    for(int i = 1; i <= n; i++)
        sort(pos[i].begin(), pos[i].end());
    for(int i = 1; i <= n; i++){
        int cur = i;
        for(int j = i; j <= n; j++){
            int it = lower_bound(pos[j].begin(), pos[j].end(), i) - pos[j].begin();
            if(it == pos[j].size()) continue;
            if(pos[j][it] > cur) continue;
            cout << i << " " << j << '\n';
            cur = j + 1;
            bp[i][j] = true;
        }
    }
    while(q--){
        int s, e;
        cin >> s >> e;
        cout << (bp[s][e] ? "YES" : "NO") << '\n';
    }
    exit(0);
}

bool bp2[ars];
int mn[ars];
void sub4(){
    for(int i = 1; i <= n; i++)
        mn[i] = n + 1;
    for(int i = 1; i <= m; i++){
        cin >> a[i].fi >> a[i].se;
        mn[a[i].se] = min(mn[a[i].se], a[i].fi);
    }
    int cur = 1;
    for(int i = 1; i <= n; i++){
        if(mn[i] <= cur){
            cur = i + 1;
            bp2[i] = true;
        }
    }
    while(q--){
        int s, e;
        cin >> s >> e;
        cout << (bp2[e] ? "YES" : "NO") << '\n';
    }
    exit(0);
}

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){
    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, mid + 1, r, u, v, ul, ur);
}

pll 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, st[id].mx >= l};
    }

    pll 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);

    if(st[id].lef != -1){
        if(a.fi >= st[id].lef){
            a.fi = max(a.fi, (ll)st[id].rig);
            a.se = 1;
        }
    }
    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){
        if(t == 0)
            update(1, 1, n, 1, l, l - 1, r);
        else{
            auto cur = get(1, 1, n, l);
            if(cur.fi >= r && cur.se){
                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();
}

Compilation message (stderr)

curtains.cpp: In function 'int main()':
curtains.cpp:188:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  188 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
curtains.cpp:189:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  189 |         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...