Submission #1100069

#TimeUsernameProblemLanguageResultExecution timeMemory
1100069NoMercyCurtains (NOI23_curtains)C++17
100 / 100
733 ms55872 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int inf = 1e9 + 199; #define left v + 1 #define right v + 2 * (mid - l) struct Lazy_Segree { struct pi { int mn = 0, lazy = 0, mark = 0; } emp; vector<pi> tree; void init (int x) { tree.assign (x << 1, emp); } void push (int v, int l, int r) { if (tree[v].mark == 0 || l == r) return; int mid = (l + r) >> 1; tree[left].mn = max(tree[left].mn, tree[v].lazy); tree[right].mn = max(tree[right].mn, tree[v].lazy); tree[left].lazy = max(tree[left].lazy, tree[v].lazy); tree[right].lazy = max(tree[right].lazy, tree[v].lazy); tree[v].mark = tree[v].lazy = 0; tree[left].mark = tree[right].mark = 1; } void update (int v, int l, int r, int ml, int mr, int val) { if (l == r || l >= mr || ml >= r) return; if (ml <= l && r <= mr) { tree[v].mn = max(tree[v].mn, val); tree[v].lazy = max(tree[v].lazy, val); tree[v].mark = 1; return; } push (v, l, r); int mid = (l + r) >> 1; update (left, l, mid, ml, mr, val); update (right, mid, r, ml, mr, val); tree[v].mn = min(tree[left].mn, tree[right].mn); } int get (int v, int l, int r, int ml, int mr) { if (l == r || l >= mr || ml >= r) return inf; if (ml <= l && r <= mr) { return tree[v].mn; } push (v, l, r); int mid = (l + r) >> 1; return min(get (left, l, mid, ml, mr), get (right, mid, r, ml, mr)); } }; int32_t main () { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N, M, Q; cin >> N >> M >> Q; vector<array<int, 2>> all; for (int i = 0;i < M;i ++) { int l, r; cin >> l >> r; all.push_back({l, r}); } vector<array<int, 3>> q; for (int i = 0;i < Q;i ++) { int l, r; cin >> l >> r; q.push_back({l, r, i}); } sort(q.begin(), q.end(), [&](array<int, 3> a, array<int, 3> b) { return (a[1] < b[1]); }); sort(all.begin(), all.end(), [&](array<int, 2> a, array<int, 2> b) { return (a[1] < b[1]); }); Lazy_Segree LS; LS.init (N + 1); string res[Q]; int ind = 0; // cout << "\n"; for (int i = 0;i < Q;i ++) { // cout << q[i][0] << " " << q[i][1] << "\n"; while (ind < M && all[ind][1] <= q[i][1]) { LS.update (1, 1, N + 1, all[ind][0], all[ind][1] + 1, all[ind][0]); ind ++; } if (LS.get (1, 1, N + 1, q[i][0], q[i][1] + 1) >= q[i][0]) { res[q[i][2]] = "YES"; } else { res[q[i][2]] = "NO"; } } for (int i = 0;i < Q;i ++) { cout << res[i] << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...