제출 #1117227

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1117227		hiepsimauhong	Curtains (NOI23_curtains)	C++17	0 / 100	1 ms	4600 KiB

curtains

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
const int64_t oo = 1e9;
#define int long long

#define quickly ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define print(a,l,r) for(int OK(l); OK <= r ; ++OK){ if(a[OK] < oo){cout << a[OK] <<' ';} else{cout << "- ";}} cout << '\n';
#define prints(a) for(auto i : a){ cout << i <<' ';} cout << '\n';
#define printz(a,l,r) for(int OK(1) ; OK <= l ; ++OK){for(int KO(1) ; KO <= r ; ++KO){if(a[OK][KO] < oo){cout << a[OK][KO] <<' ';}else{cout << "- ";}}cout << '\n';} cout << '\n';
#define fs first
#define sd second
#define ii pair<int,int>
#define iii pair<int, ii>
#define all(a) a.begin(), a.end()

const int N = 5e5 + 5;
const int mod = 1e9 + 7;
const int base = 1e7;

int n, m, q;
ii a[N];
int parent[N];
bool st[N], en[N];

struct Segment_tree{
        int sg[N << 2], lazy[N << 2];

        void push_down(int id, int l, int r){
                if(lazy[id]){
                        lazy[id << 1] = lazy[id];
                        sg[id << 1] = lazy[id];

                        lazy[id << 1 | 1] = lazy[id];
                        sg[id << 1 | 1] = lazy[id];

                        lazy[id] = 0;
                }
        }

        void update(int id, int l, int r, int u, int v, int val){
                if(l > v || r < u){
                        return;
                }
                if(u <= l && r <= v){
                        lazy[id] = val;
                        sg[id] = val;
                        return;
                }

                push_down(id, l, r);

                int mid = (l + r) >> 1;
                update(id << 1, l, mid, u, v, val);
                update(id << 1 | 1, mid + 1, r, u, v, val);
        }

        int get(int id, int l, int r, int pos){
                if(l > pos || r < pos){
                        return -oo;
                }
                if(l == r){
                        return sg[id];
                }

                push_down(id, l, r);

                int mid = (l + r) >> 1;
                return max(get(id << 1, l, mid, pos), get(id << 1 | 1, mid + 1, r, pos));
        }
};

Segment_tree sg;

signed main(){ quickly
        cin >> n >> m >> q;

        for(int i(1) ; i <= m ; ++i){
                cin >> a[i].fs >> a[i].sd;
                st[a[i].fs] = en[a[i].sd] = true;
                parent[i] = i;
        }

        sort(a + 1, a + 1 + m);

        sg.update(1, 1, n, a[1].fs, a[1].sd, 1);

        for(int i(2) ; i <= m ; ++i){
                if(a[i - 1].sd + 1 >= a[i].fs){
                        sg.update(1, 1, n, a[i].fs, a[i].sd, parent[i - 1]);
                        parent[i] = parent[i - 1];
                }
                else{
                        sg.update(1, 1, n, a[i].fs, a[i].sd, i);
                }
        }

        while(q--){
                int l, r;
                cin >> l >> r;
                if(st[l] && en[r] && sg.get(1, 1, n, l) == sg.get(1, 1, n, r)){
                        cout << "YES\n";
                }
                else{
                        cout << "NO\n";
                }
        }
}

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