Submission #1259752

#TimeUsernameProblemLanguageResultExecution timeMemory
1259752phtungCurtains (NOI23_curtains)C++20
9 / 100
1596 ms2492 KiB
#include <bits/stdc++.h> using namespace std; #define name "IO" #define int long long const int inf = 1e18 + 7; const int maxn = 5e5 + 5; int n, m, q; struct segTree { vector<int> st, lazy; segTree(int n) { st.resize(4 * n + 5, 0); lazy.resize(4 * n + 5, 0); } void clear() { fill(st.begin(), st.end(), 0); fill(lazy.begin(), lazy.end(), 0); } void down(int id, int l, int r) { if(!lazy[id]) return; st[id] += lazy[id]; if(l != r) { lazy[id * 2] += lazy[id]; lazy[id * 2 + 1] += lazy[id]; } lazy[id] = 0; } void update(int id, int l, int r, int u, int v, int val) { down(id, l, r); if(l > v || r < u) return; if(l >= u && r <= v) { lazy[id] += val; down(id, l, r); return; } int m = l + r >> 1; update(id * 2, l, m, u, v, val); update(id * 2 + 1, m + 1, r, u, v, val); st[id] = min(st[id * 2], st[id * 2 + 1]); } int get(int id, int l, int r, int u, int v) { down(id, l, r); if(l > v || r < u) return inf; if(l >= u && r <= v) return st[id]; int m = l + r >> 1; return min(get(id * 2, l, m, u, v), get(id * 2 + 1, m + 1, r, u, v)); } }; bool check(int u, int v, int l, int r) { if(u < l || u > r) return 0; if(v < l || v > r) return 0; return 1; } void solve() { cin >> n >> m >> q; vector<pair<int,int>> curtain; for(int i = 1; i <= m; i++) { int l, r; cin >> l >> r; curtain.push_back({l, r}); } segTree st(n); for(int i = 1; i <= q; i++) { st.clear(); int l, r; cin >> l >> r; for(auto [left, right] : curtain) { if(check(left, right, l, r)) st.update(1, 1, n, left, right, 1); } if(st.get(1, 1, n, l, r) > 0) cout << "YES\n"; else cout << "NO\n"; } } signed main() { if (fopen (name".INP", "r")) { freopen (name".INP", "r", stdin); freopen (name".OUT", "w", stdout); } ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); clock_t start = clock(); int t = 1; while(t--) solve(); std::cerr << "Time: " << clock() - start << "ms\n"; return 0; }

Compilation message (stderr)

curtains.cpp: In function 'int main()':
curtains.cpp:109:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |         freopen (name".INP", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
curtains.cpp:110:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |         freopen (name".OUT", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#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...