Submission #1116417

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116417		hngwlog	Curtains (NOI23_curtains)	C++17	100 / 100	775 ms	173220 KiB

curtains

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

#define fi first
#define se second
#define _size(x) (int)x.size()
#define BIT(i, x) ((x >> i) & 1)
#define MASK(n) ((1 << n) - 1)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define FOR(i, a, b) for (int i = a, _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = a, _b = (b); i >= _b; --i)
#define FORB1(i, mask) for (int i = mask; i > 0; i ^= i & -i)
#define FORB0(n, i, mask) for (int i = ((1 << n) - 1) ^ mask; i > 0; i ^= i & - i)
#define FORALL(i, a) for (auto i: a)
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);

struct queryNode {

    int v, id;

    bool operator < (const queryNode o) const {

        return v < o.v;
    }
};

int n, m, q;
vector<bool> ans;
vector<vector<int>> adjL, adjR, p, pRv;
vector<vector<queryNode>> query;

void DAC(int cnt, int l, int r) {

    if (l == r) {
        while (_size(query[l])) {
            if (_size(adjL[l]) && adjL[l][0] == l) ans[query[l].back().id] = 1;
            else ans[query[l].back().id] = 0;
            query[l].pop_back();
        }
        return ;
    }
    int mid = (l + r) / 2;
    int pos = lower_bound(adjL[mid].begin(), adjL[mid].end(), mid) - adjL[mid].begin();
    p[cnt][mid] = (pos == _size(adjL[mid]) ? - 1 : adjL[mid][pos]);
    stack<int> st;
    if (p[cnt][mid] != - 1) st.push(mid);
    FORD(i, mid - 1, l) {
        pos = lower_bound(adjL[i].begin(), adjL[i].end(), mid) - adjL[i].begin();
        int best = - 1;
        if (pos != _size(adjL[i])) best = adjL[i][pos];
        if (pos) {
            pos--;
            while (!st.empty() && st.top() <= adjL[i][pos] + 1) {
                if (best == - 1 || best > p[cnt][st.top()]) best = p[cnt][st.top()];
                st.pop();
            }
        }
        p[cnt][i] = best;
        if (best != - 1) st.push(i);
    }
    while (!st.empty()) st.pop();
    pos = upper_bound(adjR[mid + 1].begin(), adjR[mid + 1].end(), mid + 1) - adjR[mid + 1].begin();
    pRv[cnt][mid + 1] = (!pos ? - 1 : adjR[mid + 1][pos - 1]);
    if (pRv[cnt][mid + 1] != - 1) st.push(mid + 1);
    FOR(i, mid + 2, r) {
        pos = upper_bound(adjR[i].begin(), adjR[i].end(), mid + 1) - adjR[i].begin();
        int best = - 1;
        if (pos) best = adjR[i][pos - 1];
        if (pos != _size(adjR[i])) {
            while (!st.empty() && st.top() >= adjR[i][pos] - 1) {
                if (best == - 1 || best < pRv[cnt][st.top()]) best = pRv[cnt][st.top()];
                st.pop();
            }
        }
        pRv[cnt][i] = best;
        if (best != - 1) st.push(i);
    }
    FOR(u, l, mid) {
        int v;
        while (_size(query[u]) && (v = query[u].back().v) > mid) {
            if (p[cnt][u] == - 1 || pRv[cnt][v] == - 1 || p[cnt][u] > v || pRv[cnt][v] < u) ans[query[u].back().id] = 0;
            else ans[query[u].back().id] = 1;
            query[u].pop_back();
        }
    }
    DAC(cnt + 1, l, mid);
    DAC(cnt + 1, mid + 1, r);
}

int main() {
    fastio;

    cin >> n >> m >> q;
    adjL.resize(n + 1);
    adjR.resize(n + 1);
    REP(i, m) {
        int l, r;
        cin >> l >> r;
        adjL[l].push_back(r);
        adjR[r].push_back(l);
    }
    FOR(i, 1, n) {
        sort(adjL[i].begin(), adjL[i].end());
        sort(adjR[i].begin(), adjR[i].end());
    }
    query.resize(n + 1);
    REP(i, q) {
        int u, v;
        cin >> u >> v;
        query[u].push_back({v, i});
    }
    FOR(i, 1, n) sort(query[i].begin(), query[i].end());
    ans.resize(q);
    p.assign(20, vector<int>(n + 1));
    pRv.assign(20, vector<int>(n + 1));
    DAC(0, 1, n);
    REP(i, q) {
        if (ans[i]) cout << "YES\n";
        else cout << "NO\n";
    }
    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