제출 #886818

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
886818		tsumondai	Curtains (NOI23_curtains)	C++14	100 / 100	931 ms	95760 KiB

curtains

#include<bits/stdc++.h>
using namespace std;

namespace Solve
{
    typedef pair<long long, long long> ox;
    vector<int> events[1000001];
    vector<ox> query[1000001];
    #define fi first
    #define se second
    long long lazy[2000001], node[2000001];
    bool res[1000001];
    int n, m, q;

    void down(int id, int l, int r)
    {
        if(lazy[id] == 0) return;
        node[id] = max(node[id], lazy[id]);

        if(l != r)
        {
            lazy[id * 2] = max(lazy[id * 2], lazy[id]);
            lazy[id * 2 + 1] = max(lazy[id * 2 + 1], lazy[id]);
        }

        lazy[id] = 0;
    }

    void update(int id, int l, int r, int L, int R, int val)
    {
        down(id, l, r);
        if(l > R || r < L) return;
        if(L <= l && r <= R)
        {
            lazy[id] = val;
            down(id, l, r);
            return;
        }

        update(id * 2, l, (l + r)/2, L, R, val);
        update(id * 2 + 1, (l + r)/2 + 1, r, L, R, val);

        node[id] = min(node[id * 2], node[id * 2 + 1]);
    }

    int get(int id, int l, int r, int L, int R)
    {
        down(id, l, r);
        if(l > R || r < L) return 1e9;
        if(L <= l && r <= R)
        {
            return node[id];
        }

        return min(get(id * 2, l, (l + r)/2, L, R), get(id * 2 + 1, (l + r)/2 + 1, r, L, R));
    }

    void solve()
    {
        cin >> n >> m >> q;
        for(int i = 1; i <= m ;i++)
        {
            int l, r;
            cin >> l >> r;
            events[r].push_back(l);
        }

        for(int i = 1; i <= q; i++)
        {
            int l, r;
            cin >> l >> r;
            query[r].push_back({l, i});
        }

        for(int r = 1; r <= n; r++)
        {
            for(auto l: events[r])
            {
                update(1, 1, n, l, r, l);
            }

            for(auto it: query[r])
            {
                int l = it.fi;
                int id = it.se;

                if(get(1, 1, n, l, r) >= l)
                {
                    res[id] = 1;
                }
            }
        }

        for(int i = 1; i <= q; i++)
        {
            cout << (res[i] ? "YES\n" : "NO\n");
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);


    Solve::solve();
}

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