Submission #1315038

#	Time	Username	Problem	Language	Result	Execution time	Memory
1315038		thaibaotran555	Curtains (NOI23_curtains)	C++20	0 / 100	1595 ms	2932 KiB

curtains

///TRAN THAI BAO :3

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

#define maxN 500007

int n, m, q;

typedef pair<int, int> pii;

struct segment
{
    int l, r;
};
segment inp[maxN];
int nxt[maxN] = {0};
int up[maxN][20];
vector<pii>segEnd[maxN];

bool intersect(segment x, segment y)
{
    if(y.l - x.r > 1 || x.l - y.r > 1)
        return false;
    return true;
}

void readData()
{
    cin >> n >> m >> q;
    for(int i = 1; i <= m; i++)
    {
        cin >> inp[i].l >> inp[i].r;
        segEnd[inp[i].l].push_back({inp[i].r, i});
    }
    nxt[0] = 0;
    for(int i = 1; i <= m; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            if(i == j) continue;
            if(inp[j].r <= inp[i].r)
                continue;
            if(intersect(inp[i], inp[j]))
                if(nxt[i] == 0 || inp[nxt[i]].r > inp[j].r)
                    nxt[i] = j;
        }
    }
}

void build()
{
    for(int i = 1; i <= n; i++)
        sort(segEnd[i].begin(), segEnd[i].end());
    for(int i = 1; i <= m; i++)
        up[i][0] = nxt[i];
    for(int i = 1; i < 20; i++)
        for(int j = 0; j <= m; j++)
            up[j][i] = up[up[j][i-1]][i-1];
}

bool query(int u, int v)
{
    int start = 0;
    int lo = 0, hi = segEnd[u].size()-1;
    while(lo <= hi)
    {
        int mid = (lo+hi)/2;
        if(segEnd[u][mid].first <= v)
        {
            start = segEnd[u][mid].second;
            lo = mid+1;
        }
        else hi = mid-1;
    }
    if(start == 0)
        return false;
    for(int i = 19; i >= 0; i--)
        if(up[start][i] != 0 && inp[up[start][i]].r <= v)
            start = up[start][i];
    return inp[start].r == v;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    readData();
    build();
    int u, v;
    while(q--)
    {
        cin >> u >> v;
        if(query(u, v))
            cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}

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