Submission #1767277

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define REP(i, a, b) for (int i = (a), i##_end_ = (b); i < i##_end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()

template<typename T> inline bool chkmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

typedef long long LL;

const int oo = 0x3f3f3f3f;

const int maxn = 100100;

int n, qn;

pair<int, int> a[maxn + 5];

vector<pair<int, int> > all[maxn + 5];
int b[maxn + 5];

bool used[maxn + 5];

int sum[maxn + 5];

int Min[maxn + 5];

int dis[maxn + 5];

inline int init()
{
	memset(used, 0, sizeof used);
	set<pair<int, int> > cur;
	int ret = 0;
	sum[n + 1] = 0;
	for (int i = n; i >= 0; --i)
	{
		sum[i] += sum[i + 1];
		for (auto u : all[i]) --sum[i], cur.insert(u);
		while (sum[i] < i - n)
		{
			if (cur.empty() || cur.begin()->x >= i)
			{
				return -1;
			}
			++ret;
			++sum[i];
			--sum[cur.begin()->x];
			used[cur.begin()->y] = 1;
			cur.erase(*cur.begin());
		}
	}
	REP(i, 0, n + 1) sum[i] = 0;
	memset(Min, oo, sizeof Min);
	REP(i, 0, n - 1) 
		if (!used[i])
		{
			--sum[a[i].x];
			chkmin(Min[a[i].x], a[i].y);
		}
		else --sum[a[i].y];
	Min[n + 1] = oo;
	for (int i = n; i >= 0; --i)
	{
		chkmin(Min[i], Min[i + 1]);
	}
	for (int i = n - 1; i >= 0; --i) sum[i] += sum[i + 1];
	REP(i, 0, n + 1) sum[i] += n - i;
	vector<int> zeros;
	REP(i, 0, n + 1) if (!sum[i]) zeros.pb(i);
	memset(dis, oo, sizeof dis);
	dis[0] = 0;
	REP(i, 1, n + 1)
	{
		if (!sum[i]) 
		{
			if (Min[i] < i) chkmin(dis[i], dis[Min[i]] + 1);
		}
		else dis[i] = dis[i - 1];
	}
	return ret;
}

int main()
{
#ifdef matthew99
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	scanf("%d", &n);
	++n;
	REP(i, 0, n - 1) scanf("%d%d", &a[i].x, &a[i].y);
	REP(i, 0, n) scanf("%d", b + i);
	sort(b, b + n);
	REP(i, 0, n - 1) 
	{
		a[i].x = lower_bound(b, b + n, a[i].x) - b, a[i].y = lower_bound(b, b + n, a[i].y) - b;
		all[a[i].x].pb(mp(a[i].y, i));
	}

	scanf("%d", &qn);

	int A = init();
	if (!~A)
	{
		REP(i, 0, qn) printf("-1\n");
	}
	else
	{
		REP(i, 0, qn)
		{
			int x, y;
			scanf("%d%d", &x, &y);
			x = lower_bound(b, b + n, x) - b, y = lower_bound(b, b + n, y) - b;
			int ans = min(A + dis[x], A + 1 + dis[y]);
			if (ans >= oo) printf("-1\n");
			else printf("%d\n", n - ans);
		}
	}
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:98:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
./Main.cpp:100:50: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  REP(i, 0, n - 1) scanf("%d%d", &a[i].x, &a[i].y);
                                                  ^
./Main.cpp:101:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  REP(i, 0, n) scanf("%d", b + i);
                                 ^
./Main.cpp:109:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &qn);
                  ^
./Main.cpp:121:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    sc...

Judge Result