Submission #1165181

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165181		Rhael	Curtains (NOI23_curtains)	C++17	0 / 100	1 ms	328 KiB

curtains

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define INF make_pair((int)1e9,0)
using namespace std;
const int MAXN=500005;
struct Segtree{
    vector<vector<int>> root;
    int N;
    void build(int _N){
        root.resize(4*_N);
        this->N=_N;
    }
    void update(int start,int end,int L,int R,int node){
        if(L==R){
            root[node].emplace_back(end);
            return;
        }
        int mid=(L+R)/2;
        if(start<=mid) update(start,end,L,mid,node*2);
        else update(start,end,mid+1,R,node*2+1);
    }
    void update_all(int L,int R,int node){
        if(L==R) return;
        int mid=(L+R)/2;
        update_all(L,mid,node*2);
        update_all(mid+1,R,node*2+1);
        int itL=0,itR=0,LN=node*2,RN=LN+1;
        while(itL<root[LN].size()&&itR<root[RN].size()){
            if(root[LN][itL]<=root[RN][itR]) root[node].emplace_back(root[LN][itL++]);
            else if(root[node].empty()||root[node].back()<=mid) itR++;
            else root[node].emplace_back(root[RN][itR++]);
        }
        while(itL<root[LN].size()) root[node].emplace_back(root[LN][itL++]);
        while(!root[node].empty()&&root[node].back()>mid&&itR<root[RN].size())
            root[node].emplace_back(root[RN][itR++]);  
    }
    pair<int,int> query(int start,int end,int L,int R,int node){
        if(R<start||L>end) return INF;
        if(start<=L&&R<=end){
            if(root[node].empty()) return INF;
            auto it=upper_bound(root[node].begin(),root[node].end(),end);
            if(it==root[node].begin()) return INF;
            return make_pair(L,*prev(it));
        }
        int mid=(L+R)/2;
        auto AnsL=query(start,end,L,mid,node*2);
        auto AnsR=query(start,end,mid+1,R,node*2+1);
        if(AnsL==INF) return AnsR;
        if(AnsR==INF) return AnsL;
        return (AnsR.first>AnsL.second)?INF:make_pair(AnsL.first,AnsR.second);
    }
    void update_test(int start,int end){
        update(start,end,1,N,1);
    }
    bool query_test(int start,int end){
        return make_pair(start,end)==query(start,end,1,N,1);
    }
} Tree;
vector<pair<int,int>> tmp;
int n,m,k;
int a,b;
// ifstream File("input.txt");
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    bool ok=1;
    cin >> n >> m >> k;
    Tree.build(n);
    for(int i=0;i<m;i++){
        cin >> a >> b;
        tmp.emplace_back(a,b+1);
    }
    sort(tmp.begin(),tmp.end());
    for(int i=0;i<m;i++) Tree.update_test(tmp[i].first,tmp[i].second);
    Tree.update_all(1,n,1);
    for(int i=0;i<k;i++) cin >> a >> b,cout << (Tree.query_test(a,b+1)?"YES\n":"NO\n");
    
    return 0;
}
/*
8 2 1
1 5
2 6
1 4
*/

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