Submission #1172959

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172959		DangKhoizzzz	Curtains (NOI23_curtains)	C++17	100 / 100	900 ms	68316 KiB

curtains

#include <bits/stdc++.h>
#define pii pair <int , int>
#define fi first
#define se second

using namespace std;

const int INF = 1e9;
const int maxn = 5e5 + 7;


struct modified_Segment_Tree
{
    int st[maxn*4] , lazy[maxn*4];

    void init()
    {
        for(int i = 1; i < maxn*4; i++) st[i] = lazy[i] = INF;
    }

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

        st[id] = min(st[id] , lazy[id]);

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

    void update(int id , int l , int r , int u , int v , int val)
    {
        down(id , l , r);
        if(r < u || l > v) return;
        if(u <= l && r <= v)
        {
            lazy[id] = val;
            down(id , l , r);
            return;
        }
        int mid = (l+r) >> 1;
        update(id*2 , l , mid , u , v , val);
        update(id*2+1 , mid+1 , r , u , v , val);
        st[id] = max(st[id*2] , st[id*2+1]);
    }

    int get(int id , int l , int r , int u , int v)
    {
        down(id , l , r);
        if(r < u || l > v) return -INF;
        if(u <= l && r <= v) return st[id];
        int mid = (l+r) >> 1;
        int Lget = get(id*2 , l , mid , u , v);
        int Rget = get(id*2+1 , mid+1 , r , u , v);
        return max(Lget , Rget);
    }
};

int n , m , q;
modified_Segment_Tree ST;
vector <int> Rg[maxn];
vector <pii> query[maxn];

bool ans[maxn];

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

    ST.init();

    for(int l = n; l >= 1; l--)
    {
        for(int r: Rg[l]) ST.update(1 , 1 , n , l , r , r);
        
        for(pii tmp: query[l])
        {
            int r = tmp.fi , id = tmp.se;
            if(ST.get(1 , 1 , n , l , r) == r) ans[id] = 1;
        }

    }

    for(int i = 1; i <= q; i++)
    {
        if(ans[i]) cout << "YES" << '\n';
        else cout << "NO" << '\n';
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

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