제출 #1329791

#제출 시각아이디문제언어결과실행 시간메모리
1329791viduxGift Exchange (JOI24_ho_t4)C++17
100 / 100
1597 ms246204 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll, ll> pll;
const ll INF = 1e9;
struct SegMx {
        int n;
        vl t;
        SegMx(int sz) {
                n = sz;
                t = vl(2*n, -1);
        } 
        void update(int p, ll v) {
                for (t[p += n] = v; p > 1; p /= 2) t[p/2] = max(t[p], t[p^1]);
        }
        ll query(int l, int r) {
                ll res = -1;
                for (l += n, r += n; l < r; l /= 2, r /= 2) {
                        if (l&1) res = max(res, t[l++]);
                        if (r&1) res = max(res, t[--r]);
                }
                return res;
        }
};
struct Tag {
	bool set = 0;
	ll v = 0;
};
struct SegMnLz {
	int n;
	vl t; 
	vector<Tag> lz;
	SegMnLz(int sz) {
		n = sz;
		t = vl(4*n, INF);
		lz = vector<Tag>(4*n, {0, INF});
	}
private:
	void apply(int id, Tag q) {
		if (q.set) {
			lz[id].set = 1;
			lz[id].v = min(lz[id].v, q.v);
			t[id] = min(t[id], q.v);
		}
	}
	void push_down(int id, int l, int r) {
		if (!lz[id].set) return;
		apply(id*2, lz[id]);
		apply(id*2+1, lz[id]);
		lz[id] = Tag{0, INF};
	}
	void update(int id, int l, int r, int ql, int qr, Tag q) {
		if (qr <= l || ql >= r) return;
		if (ql <= l && r <= qr) apply(id, q);
		else {
			push_down(id, l, r);
			int m = (l+r)/2;
			update(2*id, l, m, ql, qr, q);
			update(2*id+1, m, r, ql, qr, q);
			t[id] = min(t[id*2], t[id*2+1]);
		}
	}
	ll query(int id, int l, int r, int ql, int qr) {
		if (qr <= l || ql >= r) return INF;
		if (ql <= l && r <= qr) return t[id];
		push_down(id, l, r);
		int m = (l+r)/2;
		return min(query(id*2, l, m, ql, qr), query(id*2+1, m, r, ql, qr));
	}
public:
	void update(int l, int r, ll v) {
		update(1, 0, n, l, r, Tag{1, v});
	}
	ll query(int l, int r) {
		return query(1, 0, n, l, r);
	}
};
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n; cin >> n;
	vl a(n), b(n);
	for (auto &i : a) cin >> i;
	for (auto &i : b) cin >> i;

	vl pr(n, n), nx(n, n);
	int r = 0;
	vector<vl> rem(n);
	SegMx seg(n);
	SegMnLz sufseg(n*2);
	for (int i = n-1; i >= 0; i--) {
		int l = b[i], r = a[i];
		int cnx = sufseg.query(l, r+1);
		nx[i] = cnx;
		sufseg.update(l, r+1, i);
	}
	SegMnLz preseg(n*2);
	for (int i = 0; i < n; i++) {
		int l = b[i], r = a[i];
		int cpr = -preseg.query(l, r+1);
		pr[i] = cpr;
		if (cpr != -INF) rem[cpr].push_back(i);
		else seg.update(i, nx[i]);
		preseg.update(l, r+1, -i);
	}
	int q; cin >> q;
	vector<pair<pll, int>> qs(q);
	for (int i = 0; i < q; i++) cin >> qs[i].first.first >> qs[i].first.second, qs[i].first.first--, qs[i].first.second--, qs[i].second = i;
	sort(qs.begin(), qs.end());
	vl ans(q);
	int reml = 0;
	for (auto [lr, qid] : qs) {
		auto [l, r] = lr;
		while (reml < l) {
			for (auto j : rem[reml]) seg.update(j, nx[j]);
			reml++;
		}
		ll mx = seg.query(l, r+1);
		ans[qid] = mx <= r;
	}
	for (auto ok : ans) cout << (ok ? "Yes" : "No") << endl;
}
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...