Submission #1238096

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238096		meisean2009	Curtains (NOI23_curtains)	C++20	0 / 100	8 ms	12104 KiB

curtains

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n,m,q;
struct LazySeg {
    int n;
    vector<ll> seg;
    vector<ll> lazy; // dirt
    void init(int _n) {
        for (n = 1; n < _n; n *= 2);
        seg = lazy = vector<ll>(2 * n,-1);
    }
    void pull(int i) {
        seg[i] = max(seg[2 * i],seg[2 * i + 1]);
    }
    void push(int i, int l, int r) {
        if (l + 1 < r) {
            lazy[2 * i] = max(lazy[2*i],lazy[i]);
            lazy[2 * i + 1] = max(lazy[2*i+1],lazy[i]);
        }
        seg[i] = max(seg[i],lazy[i]);//applying lazy
        lazy[i] = -1;
    }
    void update(int lo, int hi, ll v, int i, int l, int r) {
        push(i, l, r);
        if (lo >= r || hi <= l) return;
        if (lo <= l && r <= hi) {
            lazy[i] = max(lazy[i],v);
            push(i, l, r);
            return;
        }
        int m = (l + r) / 2;
        update(lo, hi, v, 2 * i, l, m);
        update(lo, hi, v, 2 * i + 1, m, r);
        pull(i);
    }
    //range min query
    //range max update
    ll query(int lo, int hi, int i, int l, int r) {
        push(i, l, r);
        if (lo >= r || hi <= l) return INT_MAX;
        if (lo <= l && r <= hi) return seg[i];
        int m = (l + r) / 2;
        return min(query(lo, hi, 2 * i, l, m),query(lo, hi, 2 * i + 1, m, r));
    }
    void upd(int l, int r, ll v) {
        update(l, r, v, 1, 0, n);
    }
    ll qry(int l, int r) {
        return query(l, r, 1, 0, n);
    }
};
typedef pair<int,int> p;
#define f first 
#define s second 
vector<p> curts,order;
vector<int> queries[500005];
map<p,int> ans;
int main(){
    //freopen("c_in.txt","r",stdin);
    cin>>n>>m>>q;    
    LazySeg seg;
    seg.init(n);
    for (int i=0;i<m;i++){
        int a,b;cin>>a>>b;
        a--;b--;
        curts.push_back({b,a});//sort by right element
    }

    for (int i=0;i<q;i++){
        int a,b;cin>>a>>b;
        a--;b--;
        order.push_back({a,b});
        queries[b].push_back(a);//fix right
    }
    int ptr=0;
    sort(curts.begin(),curts.end());
    for (int i=0;i<n;i++){
        while (ptr<m&&curts[ptr].f<=i){
            int rit = curts[ptr].f,lef=curts[ptr].s;
            seg.upd(lef,rit+1,lef); //setting everything in range to max of its left value
            ptr++;
        }
        for (int x:queries[i]){
            int res = seg.qry(x,i+1);
            if (res<x){
                ans[{x,i}]=0;
            }else{
                ans[{x,i}]=1;
            }
        }
    }
    for (auto [x,y]:order){
        int res = ans[{x,y}];
        if (res==0){
            cout<<"NO";
        }else{
            cout<<"YES";
        }
        cout<<endl;
    }
    
}

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