Submission #1014093

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014093		Ariadna	Curtains (NOI23_curtains)	C++14	9 / 100	1556 ms	13512 KiB

curtains

#include <bits/stdc++.h>

using namespace std;

struct Segtree {
    int n;
    vector<int> st, lz;

    Segtree(const int N) {
        n = N;
        st = vector<int>(4*n, 0);
        lz = vector<int>(4*n, 0);
    }

    void push(int p, int l, int r) {
        if (lz[p] == 0) return;
        if (l != r) {
            st[2*p] += lz[p];
            st[2*p+1] += lz[p];
            lz[2*p] += lz[p];
            lz[2*p+1] += lz[p];
        }
        lz[p] = 0;
    }

    void add(int p, int l, int r, int i, int j, int v) {
        if (i > j) return;
        push(p, l, r);
        if (l == i && r == j) {
            st[p] += v;
            lz[p] += v;
        } else {
            int m = (l+r)/2;
            add(2*p, l, m, i, min(m, j), v);
            add(2*p+1, m+1, r, max(m+1, i), j, v);
            st[p] = min(st[2*p], st[2*p+1]);
        }
    }

    int Min(int p, int l, int r, int i, int j) {
        if (i > j) return 1e9;
        push(p, l, r);
        if (l == i && r == j) return st[p];
        int m = (l+r)/2;
        return min(Min(2*p, l, m, i, min(m, j)), Min(2*p+1, m+1, r, max(i, m+1), j));
    }

    void add(int i, int j, int v) { add(1, 0, n-1, i, j, v); }
    int Min(int i, int j) { return Min(1, 0, n-1, i, j); }
};

int main() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<pair<int, int>> curtains(m);
    for (int i = 0; i < m; ++i) {
        cin >> curtains[i].first >> curtains[i].second;
        --curtains[i].first; --curtains[i].second;
    }

    vector<pair<pair<int, int>, int>> queries(q);
    for (int i = 0; i < q; ++i) {
        cin >> queries[i].first.first >> queries[i].first.second;
        --queries[i].first.first; --queries[i].first.second;
        queries[i].second = i;
    }

    sort(curtains.begin(), curtains.end());
    sort(queries.begin(), queries.end());

    vector<bool> ans_query(q);
    Segtree Stage(n);

    int min_j = 0;
    unordered_set<int> used, up;
    for (int i = 0; i < q; ++i) {
        int l = queries[i].first.first, r = queries[i].first.second;

        for (int j: used) {
            if (curtains[j].first >= l && curtains[j].second <= r) continue;
            Stage.add(curtains[j].first, curtains[j].second, -1);
            up.insert(j);
        }

        for (int j: up) used.erase(j);
        up.clear();

        for (int j = min_j; j < m && curtains[j].first <= r; ++j) {
            if (curtains[j].first < l) {
                min_j = j+1;
                continue;
            }
            if (curtains[j].second <= r) {
                if (used.find(j) == used.end()) {
                    Stage.add(curtains[j].first, curtains[j].second, 1);
                    used.insert(j);
                }
            }
        }

        ans_query[queries[i].second] = (Stage.Min(l, r)>0);
    }

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

    return 0;
}

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