제출 #1315635

#제출 시각아이디문제언어결과실행 시간메모리
1315635am_aadvikJoker (BOI20_joker)C++20
0 / 100
196 ms14332 KiB
#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<map>
#include<set>
#include<cstring>
#include<stdlib.h>
#include<stdio.h>
#include<algorithm>
#include<math.h>

#define int long long
const int maxn = 200005;
const int maxm = 505;
const int maxs = 2005;
const int mod = 998244353;
const int inf = 1e17;
using namespace std;

#if 0
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
#endif

#if 0
class DSU {
public:
	vector<int> p, rank;
	DSU(int n) {
		p.resize(n), rank.resize(n, 1);
		for (int i = 0; i < n; ++i) p[i] = i;
	}

	int fset(int x) { return p[x] = ((p[x] == x) ? x : fset(p[x])); }
	bool iset(int x, int y) { return fset(x) == fset(y); }
	void uset(int x, int y) {
		x = fset(x), y = fset(y);
		if (x == y) return;
		if (rank[x] > rank[y]) swap(x, y);
		p[x] = y, rank[y] += rank[x];
	}
};
#endif

#if 1
class segtree {
private:
	vector<int> st, lazy, a;
	const int dv = 0;
	const int ldv = 0;
	int join(int l, int r) {
		return l + r;
	}
	int ljoin(int l, int r) {
		return l + r;
	}
	void upd(int s, int e, int node, int val) {
		if (val == ldv) return;
		st[node] += ((e - s + 1) * val);
	}

	int build(int s, int e, int node) {
		if (s == e)
			return st[node] = a[s];
		int mid = (s + e) / 2;
		return st[node] = join(build(s, mid, node * 2), build(mid + 1, e, node * 2 + 1));
	}

	void update(int s, int e, int node, int l, int r, int val) {
		if ((l > e) || (r < s)) return;
		if ((l <= s) && (r >= e)) {
			upd(s, e, node, val);
			lazy[node] = ljoin(lazy[node], val);
			return;
		}

		int mid = (s + e) / 2;
		upd(s, mid, node * 2, lazy[node]);
		upd(mid + 1, e, node * 2 + 1, lazy[node]);
		lazy[node * 2] = ljoin(lazy[node * 2], lazy[node]);
		lazy[node * 2 + 1] = ljoin(lazy[node * 2 + 1], lazy[node]);
		lazy[node] = ldv;

		update(s, mid, node * 2, l, r, val);
		update(mid + 1, e, node * 2 + 1, l, r, val);
		st[node] = join(st[node * 2], st[node * 2 + 1]);
	}

	int query(int s, int e, int node, int l, int r) {
		if ((l > e) || (r < s)) return dv;
		if ((l <= s) && (r >= e)) return st[node];

		int mid = (s + e) / 2;
		upd(s, mid, node * 2, lazy[node]);
		upd(mid + 1, e, node * 2 + 1, lazy[node]);
		lazy[node * 2] = ljoin(lazy[node * 2], lazy[node]);
		lazy[node * 2 + 1] = ljoin(lazy[node * 2 + 1], lazy[node]);
		lazy[node] = ldv;

		return join(query(s, mid, node * 2, l, r),
			query(mid + 1, e, node * 2 + 1, l, r));
	}

public:
	segtree(int n, vector<int> arr) {
		a = arr;
		st.resize(4 * n, dv);
		lazy.resize(4 * n, ldv);
		build(0, n - 1, 1);
	}

	int query(int l, int r) {
		return query(0, a.size() - 1, 1, l, r);
	}

	void update(int l, int r, int val) {
		update(0, a.size() - 1, 1, l, r, val);
	}
};
#endif

#if 0
int p[200005][20], dep[200005];
vector<int> g[200005];

void dfs(int node, int par) {
	p[node][0] = par;
	dep[node] = dep[par] + 1;
	for (int i = 1; i < 20; ++i)
		p[node][i] = p[p[node][i - 1]][i - 1];
	for (auto x : g[node])
		if (x != par) dfs(x, node);
}

int kpar(int node, int k) {
	for (int i = 0; i < 20; ++i)
		if (k & (1 << i))
			node = p[node][i];
	return node;
}

int lca(int u, int v) {
	if (dep[u] < dep[v]) swap(u, v);
	u = kpar(u, dep[u] - dep[v]);
	if (u == v) return u;
	for (int i = 19; i >= 0; --i)
		if (p[u][i] != p[v][i])
			u = p[u][i],
			v = p[v][i];
	return p[u][0];
}
#endif

#if 0
class line {
public:
	int m, c;
	line(int a = 0, int b = 0) { m = a, c = b; }
	int y(int x) { return m * x + c; }
};

class CHT {
private:
	int i = 0;
	vector<line> arr;

	bool bad(line a, line b, line c) {
		if (b.m == c.m) return b.c >= c.c;
		double x = (c.c - a.c) / (a.m - c.m);
		double y = (b.c - a.c) / (a.m - b.m);
		return ((y - x) > (double)(1e-6));
	}

public:
	void add(int m, int c) {
		line l(m, c);
		if (arr.size() < 2) {
			if (arr.size() == 1)
				if (arr.back().m == m)
					if (arr.back().c >= c)
						arr.pop_back();
			arr.push_back(l);
			return;
		}

		while (arr.size() > 1) {
			line pprev = arr[arr.size() - 2], prev = arr.back();
			if (!bad(pprev, prev, l)) break;
			arr.pop_back();
		}
		arr.push_back(l);
	}

	int query(int x) {
		if (arr.empty()) return inf;
		if (i >= arr.size()) i = arr.size() - 1;
		while (i < (arr.size() - 1)) {
			int cur = arr[i].y(x);
			int nxt = arr[i + 1].y(x);
			if (nxt > cur) break;
			++i;
		}
		return arr[i].y(x);
	}
};
#endif

vector<int> g[maxn];
void solve() {
	int n, m, q; cin >> n >> m >> q;
	vector<pair<int, int>> edg;
	for (int i = 0; i < m; ++i) {
		int u, v; cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
		edg.push_back({ u,v });
	}
	vector<int> col(n + 1, -1), deg(n + 1, 0), bs(m);
	int r = 0;
	for (int l = 0; l < m; ++l) {
		for (; (r < m); ++r) {
			int u = edg[r].first, v = edg[r].second;
			if ((min(col[u], col[v]) == -1))
				col[u] = max(col[u], col[v]),
				col[v] = max(col[v], col[u]);
			if (col[u] != col[v]) break;
			++deg[u], ++deg[v];
		}
		bs[l] = r - 1;
		int u = edg[l].first, v = edg[r].second;
		--deg[u], --deg[v];
		if (deg[u] == 0) col[u] = -1;
		if (deg[v] == 0) col[v] = -1;
	}
	while (q--) {
		int x, y; cin >> x >> y; --x, --y;
		cout << ((y >= bs[x]) ? "NO" : "YES") << endl;
	}
}
int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int t = 1;
	///cin >> t;
	while (t--) {
		solve();
	}
	return 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...