Submission #1006105

#TimeUsernameProblemLanguageResultExecution timeMemory
1006105WhisperCurtains (NOI23_curtains)C++17
100 / 100
905 ms87596 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define int long long #define FOR(i, a, b) for (int i = (a); i <= (b); i++) #define FORD(i, a, b) for (int i = (b); i >= (a); i --) #define REP(i, n) for (int i = 0; i < (n); ++i) #define REPD(i, n) for (int i = 👎 - 1; i >= 0; --i) #define MASK(i) (1LL << (i)) #define BIT(x, i) (((x) >> (i)) & 1) constexpr ll LINF = (1ll << 60); constexpr int INF = (1ll << 30); constexpr int Mod = 1e9 + 7; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); /* Phu Trong from Nguyen Tat Thanh High School for gifted student */ template <class X, class Y> bool minimize(X &x, const Y &y){ X eps = 1e-9; if (x > y + eps) {x = y; return 1;} return 0; } template <class X, class Y> bool maximize(X &x, const Y &y){ X eps = 1e-9; if (x + eps < y) {x = y; return 1;} return 0; } #define MAX 500005 int nArr, nCurtain, numQuery; vector<int> event[MAX]; vector<pair<int, int>> Q[MAX]; int lz[MAX * 4], st[MAX * 4]; void pushDown(int id){ if (!lz[id]) return; maximize(st[id << 1], lz[id]); maximize(st[id << 1 | 1], lz[id]); maximize(lz[id << 1], lz[id]); maximize(lz[id << 1 | 1], lz[id]); lz[id] = 0; } void upd(int id, int l, int r, int u, int v, int val){ if (u > r || v < l) return; if (u <= l && v >= r){ maximize(st[id], val); maximize(lz[id], val); return; } int m = (l + r) >> 1; pushDown(id); upd(id << 1, l, m, u, v, val); upd(id << 1 | 1, m + 1, r, u, v, val); st[id] = min(st[id << 1], st[id << 1 | 1]); } int query(int id, int l, int r, int u, int v){ if (u > r || v < l) return 1e9; if (u <= l && v >= r) return st[id]; int m = (l + r) >> 1; pushDown(id); int ql = query(id << 1, l, m, u, v); int qr = query(id << 1 | 1, m + 1, r, u, v); return min(ql, qr); } int ans[MAX]; void process(void){ cin >> nArr >> nCurtain >> numQuery; for (int i = 1; i <= nCurtain; ++i){ int l, r; cin >> l >> r; event[r].emplace_back(l); } for (int i = 1; i <= numQuery; ++i){ int l, r; cin >> l >> r; Q[r].emplace_back(l, i); } for (int r = 1; r <= nArr; ++r){ for (int &l : event[r]){ upd(1, 1, nArr, l, r, l); } for (auto&[l, i] : Q[r]){ ans[i] = (query(1, 1, nArr, l, r) >= l); } } for (int i = 1; i <= numQuery; ++i){ cout << (ans[i] ? "YES" : "NO") << "\n"; } } signed main(){ #define name "Whisper" cin.tie(nullptr) -> sync_with_stdio(false); //freopen(name".inp", "r", stdin); //freopen(name".out", "w", stdout); process(); }
#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...