Submission #1014080

#TimeUsernameProblemLanguageResultExecution timeMemory
1014080AriadnaCurtains (NOI23_curtains)C++14
9 / 100
1594 ms10648 KiB
#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) { int m = (l+r)/2; 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> used(m, false), ans_query(q); Segtree Stage(n); int last_used = 0; for (int i = 0; i < q; ++i) { int l = queries[i].first.first, r = queries[i].first.second; for (int j = 0; j < m && curtains[j].first <= r; ++j) { if (curtains[j].first >= l && curtains[j].second <= r) continue; if (used[j]) Stage.add(curtains[j].first, curtains[j].second, -1); used[j] = false; } for (int j = 0; j < m && curtains[j].first <= r; ++j) { if (curtains[j].first < l) continue; if (curtains[j].second <= r) { if (!used[j]) Stage.add(curtains[j].first, curtains[j].second, 1); used[j] = true; } } 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; }

Compilation message (stderr)

curtains.cpp: In member function 'void Segtree::push(int, int, int)':
curtains.cpp:18:17: warning: unused variable 'm' [-Wunused-variable]
   18 |             int m = (l+r)/2;
      |                 ^
curtains.cpp: In function 'int main()':
curtains.cpp:75:9: warning: unused variable 'last_used' [-Wunused-variable]
   75 |     int last_used = 0;
      |         ^~~~~~~~~
#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...